 |
|
Модераторы: Poseidon |
 
|
|
Поиск наибольшей площади 
| komlew |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 26.1.2005 Репутация: нет Всего: нет |
Всем привет!
Вот такая у меня проблемка Дана максимальная площадь n*m и координаты точек (x,y),лежащих в этой области. Начало координат в (0,0) нужно найти площадь наибольшего четерехугольника, который можно вписать в эти точки так, чтобы внутри площади точек небыло. Например дана область 10 на 10 и координаты (1,1) (1,9) (9,1) (9,9) максимальная площадь будет 80 надеюсь, что я понятно описал, заранее спасибо буду благодарен за любые идеи |
|||
|
||||
Загрузка ...
| ida |
|
|||
 замужем  Профиль Группа: Завсегдатай Сообщений: 2277 Регистрация: 14.5.2002 Где: Санкт-Петербург Репутация: нет Всего: 58 |
Попой чую, что задача из серии "исследование операций". Или с помощью производной решается. Но суть пока не уловил.
Для начала можно составить систему неравенств - обозначить как переменные те параметры, которые будут меняться, и каждое условие задачи (что чего больше, что чего меньше) выразить одним неравенством. Если увижу систему, наверное ссображу... Это сообщение отредактировал(а) ida - 26.1.2005, 09:38 |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
komlew
Прямоугольник произвольный или непременно стороны параллельны осям? -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| komlew |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 26.1.2005 Репутация: нет Всего: нет |
стороны прямоугольника лежат параллельно осям координат
да, полное описание задачи есть тут на английском http://acm.uva.es/p/v100/10043.html |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
Можно попробовать простейший перебор. Берем координаты по одной из осей, сортируем. Берем любую пару (тут и есть перебор) и для нее ищем максимальную промежность по второй координате и считаем площадь. Перебираем все пары, остается максимум..
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| EKoshelev |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 509 Регистрация: 1.9.2004 Репутация: нет Всего: нет |
komlew
Слушай, я минут семь тормозил и всё равно не понял (по линке ходил, но там всё по американски написано). На сколько я понял задачу можно перефразировать так: Дан прямоугольник ((0, 0), (n, m)). На нём точки (причём в условии не было сказано сколько точек). Дак вот в этом прямоугольнике надо построить ДРУГОЙ, чтобы в этом ДРУГОМ не было ни одной точки. Так? Или нет? Если так, то, как мне кажется, я придумал кое-что побыстрее полного перебора... Хотя... -------------------- Вежливым и адекватным предлагаю общаться на "ты". |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 17 Всего: 454 |
EKoshelev
да, твое условие - просто нормализованное исходное. Давай свою придумку... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| komlew |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 26.1.2005 Репутация: нет Всего: нет |
[b]Да, все ты правильно понял, колличество точек разве что исходной площадью ограничено. Сторона прямоугольника, который мы ищем, может так же лежать на одной из сторон ограничивающего прямоугольника Опиши свою идею, очень интересно |
|||
|
||||
| Б а Т о Н |
|
|||
 Новичок Профиль Группа: Участник Сообщений: 16 Регистрация: 30.1.2005 Где: Питер, м. Большев иков Репутация: нет Всего: 1 |
Блин, простейшие олимпиадные задачи ACM можно решать самому.
Задача имеет классическое решение. Если требуется кубическая асимптотика, то используй ДП (динамическое программирование) - d[i, j, k] - это высота наибольшего по площади прямоугольника из точки (i, j) с шириной ровно k. Если нужна квадратная асимптотика, то используй квадратную динамику и стек. Если не понятно, пиши - могу подробней написать. |
|||
|
||||
| morontt |
|
|||
 Новичок Профиль Группа: Участник Сообщений: 7 Регистрация: 4.11.2004 Где: Харьков Репутация: нет Всего: нет |
Действительно...Опиши поподробней.
Задача не такая уж и простая,как кажется на первый взгляд.И что это за асимптотики такие? Я более математик,чем программист.И асимптотики по другому как то воспринимаются. |
|||
|
||||
| Б а Т о Н |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 16 Регистрация: 30.1.2005 Где: Питер, м. Большев иков Репутация: нет Всего: 1 |
Ну честно говоря не знаю, как объяснить, не используя базовые термины; такие, как динамическая схема или асимптотика.
Если вы мне скажите, какая асимптотика (= асимптотическая сложность решения, скорость роста времени выполнения программы в зависимости от роста значений параметров) требуется, то я буду излагать конкретный алгоритм. Пока могу говорить только общими фразами. А зачем понадобилось решение этой задачи кому-то кроме komlew? Она не стоит того интереса, который к ней проявляют. Могу показать места, где таких же задач еще тысячи. Если задача здесь вызывает интерес, то может быть, ссылки кому-то покажутся интересными: acm.sgu.ru acm.uva.es acm.zju.edu.cn acm.timus.ru и т. д. (больше ссылок здесь, на моей домашней страничке в разделе ACM: http://antony.h14.ru/links.phtml) |
|||
|
||||
| morontt |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 7 Регистрация: 4.11.2004 Где: Харьков Репутация: нет Всего: нет |
 Точно,что общими фразами Программирую года с девяностого сам по себе,даже в терминологии слабовато и исключительно на бейсике  Если не впадло,то интересен алгоритм с квадратичной асимптотикой.Хотя...загляну ка я сначала на твою домашнюю. Добавлено @ 17:04 Это что...прикол? Какой ещё ЖДУ.ru  Добавлено @ 17:07 Сорри за мусор на форуме  Раздуплился  |
|||
|
||||
| morontt |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 7 Регистрация: 4.11.2004 Где: Харьков Репутация: нет Всего: нет |
 Это сообщение отредактировал(а) morontt - 30.1.2005, 17:14 |
|||
|
||||
| Б а Т о Н |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 16 Регистрация: 30.1.2005 Где: Питер, м. Большев иков Репутация: нет Всего: 1 |
А вся фишка в том, что закрывающая круглая скобка, естественно, не является частью адреса.
Таким образом, правильная ссылка такая: http://antony.h14.ru/links.phtml А алгоритм с квадратичной асимптотикой я просто так объяснить не смогу. Он довольно долго и сложно объясняется. Его, на самом деле, очень немногие знают. |
|||
|
||||
| komlew |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 26.1.2005 Репутация: нет Всего: нет |
Хмм, по моему, с квадратичной асимптотикой это самое простое решение. То, что другие придлагали, и что я в итоге и сделал. Просто берешь первую точку, и сторишь плошади со всеми остальными. Потом вторую, и так далее. Ну, специальные случаи можно еще поискать, но это тоже не будет все еще квадратично. В итоге у меня получилось O(n^2) Было интересно, можно ли эту проблему быстрее решить. |
|||
|
||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0722 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |