Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Задача Дидоны

Автор: Coder 15.10.2007, 06:54

Мне необходимо найти решение задачи Дидоны (http://ru.wikipedia.org/wiki/Задача_Дидоны) для различных входных данных.  Цитата Решением является дуга окружности, если концы нельзя двигать по побережью, и полуокружностью в противном случае. В моем случае концы можно двигать по побережью. Значит решение - полуокружность. Тогда мне нужно научиться изгибать исходную веревку различными способами, не меняя ее длину. И для каждого изгиба знать координаты узлов, чтобы найти отсеченную площадь. Еще можно решать эту задачу по формулам, которые можно найти в Интернете, но не совсем ясно, что в них значит каждый параметр и какая функция используется. На правильном я пути? И есть ли идеи по решению этой задачи?

Автор: kali 15.10.2007, 11:18

Цитата(Coder @  15.10.2007,  05:54 ) Тогда мне нужно научиться изгибать исходную веревку различными способами, не меняя ее длину. И для каждого изгиба знать координаты узлов, чтобы найти отсеченную площадь. Не совсем понятно зачем. Если Цитата(Coder @  15.10.2007,  05:54 ) В моем случае концы можно двигать по побережью. то единственным входным параметром будет длина каната L. Тогда для охвата максимальной площади точки a и b должны находится на расстоянии D=2*L/Pi друг от друга, а канат описывать полуокружность радиуса R=D/2 с центром между a и b.

Автор: Coder 15.10.2007, 13:19

Цитата(kali @  15.10.2007,  19:18 ) Тогда для охвата максимальной площади точки a и b должны находится на расстоянии D=2*L/Pi друг от друга, а канат описывать полуокружность радиуса R=D/2 с центром между a и b. А если таких точек нет? А есть на расстоянии меньше, чем D, тогда уже не получиться построить полуокружность. Здесь придется строить полуовал (как бы вытягивать нить вниз) и притом сохранить длину нити. Вот это я и имел в виду под изгибанием каната.

Автор: kali 15.10.2007, 17:08

Цитата(Coder @  15.10.2007,  05:54 ) Мне необходимо найти решение задачи Дидоны (http://ru.wikipedia.org/wiki/Задача_Дидоны) для различных входных данных.  Если линия берега прямая, то для любых входных данных задача решается аналитически. Ответ: Цитата(Coder @  15.10.2007,  05:54 ) Цитата Решением является дуга окружности, если концы нельзя двигать по побережью, и полуокружностью в противном случае.  Допустим заданы а, b и L, тогда           если L<Pi*(a-b)/2 то канат описывает дугу окружности ограниченную углом<Pi (центр окружности лежит за пределами берега)     если L>Pi*(a-b)/2 то канат описывает дугу окружности ограниченную углом>Pi (центр окружности лежит на берегу)     Если a и b не заданы, а известна только L то Цитата(kali @  15.10.2007,  10:18 ) Тогда для охвата максимальной площади точки a и b должны находится на расстоянии D=2*L/Pi друг от друга, а канат описывать полуокружность радиуса R=D/2 с центром между a и b.  Численное интегрирование необходимо только в случае когда линия берега задана какой-нибудь хитрой функцией.

Автор: Coder 16.10.2007, 01:15

Цитата(kali @  16.10.2007,  01:08 ) Если линия берега прямая, то для любых входных данных задача решается аналитически. Нет, линия берега не прямая - она произвольная (координаты берега читаются из входного файла). Я привожу рисунок. На нем нужно отсечь максимальную площадь коричневого куска со стороны моря (синий цвет) канатом длиной L. Здесь еще такая проблема: я могу пройтись по набору координат и рассчитать площадь, отсекаемую прямой между ними. Но так как многоугольник не правильный, то вычислить правильно площадь удастся не везде, а канатом обогнуть вогнутую вершину можно! Цитата(kali @  16.10.2007,  01:08 ) Численное интегрирование необходимо только в случае когда линия берега задана какой-нибудь хитрой функцией. Это этот случай?

Автор: kali 16.10.2007, 10:24

Цитата(kali @  15.10.2007,  16:08 ) Численное интегрирование необходимо только в случае когда линия берега задана какой-нибудь хитрой функцией. Это я  фигню сморозил. Вобщем ИМХО канат изгибать, в любом случае ненужно. Известно, что максимальную площадь, при заданной L, отсекает полуокружность. Получается задача сводится к перебору всех точек на линии берега, отстоящих друг от друга на расстоянии D, и выбору тех, у которых разница между выступающими и вогнутыми областями будет максимальна.

Автор: Coder 16.10.2007, 10:36

kali, спасибо за советы. попробую реализовать. потом отпишусь.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)