| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > Поиск наибольшей площади |
| Автор: komlew 26.1.2005, 03:03 |
| Всем привет! Вот такая у меня проблемка Дана максимальная площадь n*m и координаты точек (x,y),лежащих в этой области. Начало координат в (0,0) нужно найти площадь наибольшего четерехугольника, который можно вписать в эти точки так, чтобы внутри площади точек небыло. Например дана область 10 на 10 и координаты (1,1) (1,9) (9,1) (9,9) максимальная площадь будет 80 надеюсь, что я понятно описал, заранее спасибо буду благодарен за любые идеи |
| Автор: ida 26.1.2005, 09:35 |
| Попой чую, что задача из серии "исследование операций". Или с помощью производной решается. Но суть пока не уловил. Для начала можно составить систему неравенств - обозначить как переменные те параметры, которые будут меняться, и каждое условие задачи (что чего больше, что чего меньше) выразить одним неравенством. Если увижу систему, наверное ссображу... |
| Автор: Akina 26.1.2005, 09:46 |
| komlew Прямоугольник произвольный или непременно стороны параллельны осям? |
| Автор: komlew 26.1.2005, 15:25 |
| стороны прямоугольника лежат параллельно осям координат да, полное описание задачи есть тут на английском http://acm.uva.es/p/v100/10043.html |
| Автор: Akina 26.1.2005, 16:19 |
| Можно попробовать простейший перебор. Берем координаты по одной из осей, сортируем. Берем любую пару (тут и есть перебор) и для нее ищем максимальную промежность по второй координате и считаем площадь. Перебираем все пары, остается максимум.. |
| Автор: EKoshelev 27.1.2005, 12:56 |
| komlew Слушай, я минут семь тормозил и всё равно не понял (по линке ходил, но там всё по американски написано). На сколько я понял задачу можно перефразировать так: Дан прямоугольник ((0, 0), (n, m)). На нём точки (причём в условии не было сказано сколько точек). Дак вот в этом прямоугольнике надо построить ДРУГОЙ, чтобы в этом ДРУГОМ не было ни одной точки. Так? Или нет? Если так, то, как мне кажется, я придумал кое-что побыстрее полного перебора... Хотя... |
| Автор: Akina 27.1.2005, 13:54 |
| EKoshelev да, твое условие - просто нормализованное исходное. Давай свою придумку... |
| Автор: komlew 27.1.2005, 20:48 | ||
[b]Да, все ты правильно понял, колличество точек разве что исходной площадью ограничено. Сторона прямоугольника, который мы ищем, может так же лежать на одной из сторон ограничивающего прямоугольника Опиши свою идею, очень интересно |
| Автор: Б а Т о Н 30.1.2005, 03:06 |
| Блин, простейшие олимпиадные задачи ACM можно решать самому. Задача имеет классическое решение. Если требуется кубическая асимптотика, то используй ДП (динамическое программирование) - d[i, j, k] - это высота наибольшего по площади прямоугольника из точки (i, j) с шириной ровно k. Если нужна квадратная асимптотика, то используй квадратную динамику и стек. Если не понятно, пиши - могу подробней написать. |
| Автор: morontt 30.1.2005, 08:44 |
| Действительно...Опиши поподробней. Задача не такая уж и простая,как кажется на первый взгляд.И что это за асимптотики такие? Я более математик,чем программист.И асимптотики по другому как то воспринимаются. |
| Автор: Б а Т о Н 30.1.2005, 14:18 |
| Ну честно говоря не знаю, как объяснить, не используя базовые термины; такие, как динамическая схема или асимптотика. Если вы мне скажите, какая асимптотика (= асимптотическая сложность решения, скорость роста времени выполнения программы в зависимости от роста значений параметров) требуется, то я буду излагать конкретный алгоритм. Пока могу говорить только общими фразами. А зачем понадобилось решение этой задачи кому-то кроме komlew? Она не стоит того интереса, который к ней проявляют. Могу показать места, где таких же задач еще тысячи. Если задача здесь вызывает интерес, то может быть, ссылки кому-то покажутся интересными: acm.sgu.ru acm.uva.es acm.zju.edu.cn acm.timus.ru и т. д. (больше ссылок здесь, на моей домашней страничке в разделе ACM: http://antony.h14.ru/links.phtml) |
| Автор: morontt 30.1.2005, 16:59 |
 Точно,что общими фразами Программирую года с девяностого сам по себе,даже в терминологии слабовато и исключительно на бейсике  Если не впадло,то интересен алгоритм с квадратичной асимптотикой.Хотя...загляну ка я сначала на твою домашнюю. Добавлено @ 17:04 Это что...прикол? Какой ещё ЖДУ.ru  Добавлено @ 17:07 Сорри за мусор на форуме  Раздуплился  |
| Автор: morontt 30.1.2005, 17:11 |
 |
| Автор: Б а Т о Н 30.1.2005, 19:59 |
| А вся фишка в том, что закрывающая круглая скобка, естественно, не является частью адреса. Таким образом, правильная ссылка такая: http://antony.h14.ru/links.phtml А алгоритм с квадратичной асимптотикой я просто так объяснить не смогу. Он довольно долго и сложно объясняется. Его, на самом деле, очень немногие знают. |
| Автор: komlew 31.1.2005, 20:12 | ||
Хмм, по моему, с квадратичной асимптотикой это самое простое решение. То, что другие придлагали, и что я в итоге и сделал. Просто берешь первую точку, и сторишь плошади со всеми остальными. Потом вторую, и так далее. Ну, специальные случаи можно еще поискать, но это тоже не будет все еще квадратично. В итоге у меня получилось O(n^2) Было интересно, можно ли эту проблему быстрее решить. |
| Автор: Б а Т о Н 31.1.2005, 20:20 |
| Решение задачи очень сильно зависит от ограничений. Я имел в виду квадратичную по длине стороны квадрата сложность. Опиши подробно ограничения на Time Limit, количество точек, размеры большого прямоугольника. Понимаешь, что решений можно предложить массу, в зависимости от того, какой показатель является критическим и каковы возможные значения параметров. Чтобы научиться решать все задачи такого типа, советую прочитать книгу Кормена и соавторов "Алгоритмы: построение и анализ", и дальше подключать только голову. Данные задачи (ACM) имеют свойство быть очень интересными задачами на логику, программерское мышления. Решая их, можно получить массу удовольствия и сильно повысить свой алгоритмический скилл. Но для этого нужно знать базу. Без базовых знаний структур данных эти задачи решать невозможно. |
| Автор: Akina 1.2.2005, 10:07 | ||
 в общем случае ни одна из точек не обязана совпадать с вершиной прямоугольника, но на каждой из его сторон лежит минимум 1 точка. |