Мне необходимо найти решение задачи Дидоны (http://ru.wikipedia.org/wiki/Задача_Дидоны) для различных входных данных. 

В моем случае концы можно двигать по побережью. Значит решение - полуокружность. Тогда мне нужно научиться изгибать исходную веревку различными способами, не меняя ее длину. И для каждого изгиба знать координаты узлов, чтобы найти отсеченную площадь.

Еще можно решать эту задачу по формулам, которые можно найти в Интернете, но не совсем ясно, что в них значит каждый параметр и какая функция используется.

На правильном я пути? И есть ли идеи по решению этой задачи?

Это сообщение отредактировал(а) maxim1000 - 15.10.2007, 12:10

Не совсем понятно зачем.

Если

то единственным входным параметром будет длина каната L.

Тогда для охвата максимальной площади точки a и b должны находится на расстоянии D=2*L/Pi друг от друга, а канат описывать полуокружность радиуса R=D/2 с центром между a и b.

А если таких точек нет? А есть на расстоянии меньше, чем D, тогда уже не получиться построить полуокружность. Здесь придется строить полуовал (как бы вытягивать нить вниз) и притом сохранить длину нити. Вот это я и имел в виду под изгибанием каната.

Если линия берега прямая, то для любых входных данных задача решается аналитически.
Ответ:


 Допустим заданы а, b и L, тогда 
    
    если L<Pi*(a-b)/2 то канат описывает дугу окружности ограниченную углом<Pi (центр окружности лежит за пределами берега)

    если L>Pi*(a-b)/2 то канат описывает дугу окружности ограниченную углом>Pi (центр окружности лежит на берегу)

    Если a и b не заданы, а известна только L то



Численное интегрирование необходимо только в случае когда линия берега задана какой-нибудь хитрой функцией.

Нет, линия берега не прямая - она произвольная (координаты берега читаются из входного файла).
Я привожу рисунок. На нем нужно отсечь максимальную площадь коричневого куска со стороны моря (синий цвет) канатом длиной L.
Здесь еще такая проблема: я могу пройтись по набору координат и рассчитать площадь, отсекаемую прямой между ними. Но так как многоугольник не правильный, то вычислить правильно площадь удастся не везде, а канатом обогнуть вогнутую вершину можно!


Это этот случай?

Присоединённый файл ( Кол-во скачиваний: 12 )
 qwerty.jpg 7,56 Kb

Это я  фигню сморозил.

Вобщем ИМХО канат изгибать, в любом случае ненужно.

Известно, что максимальную площадь, при заданной L, отсекает полуокружность.
Получается задача сводится к перебору всех точек на линии берега, отстоящих друг от друга на расстоянии D, и выбору тех, у которых разница между выступающими и вогнутыми областями будет максимальна.

Присоединённый файл ( Кол-во скачиваний: 14 )
 qqq.GIF 3,89 Kb

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