Множества Опции

[Цири]

Помогите решить задачу!
Пусть n прямых на плоскости, заданных своими вершинами расположенными в произвольном порядке. Найти вершины наименьшего по площади многоугольника, содержащего данную точку А.

Сообщение отредактировано: Цири - 28.02.2006 3:03

[Lapp]

Пусть n прямых на плоскости, заданных своими вершинами расположенными в произвольном порядке. Найти вершины наименьшего по площади многоугольника, содержащего данную точку А.

Цири, обясни пожалуйста - при чем тут множества?? Если речь идет о множестве прямых, то это странно, а если тебе нужно использовать в проге паскалевские множества - то почему не сказал? Да и к какому месту их прикрутить?..

Задача непростая, причем в основном с точки зрения алгоритма. Я набросаю основную идею (что пришло в голову).
1. Выбираем прямую L, наиболее близкую к т.А
2. Находим основание перпендикуляра, опущенного из A на L (назовем K)
3. Находим все точки пересечения L с остальными прямыми (Mj).
4. Выбираем из них ближайшую к K, для которой векторное произведение (KA x KMj) больше нуля; называем ее N.
5. Повторяем все действия начиная с п.3 с прямой Lj (которая породила Mj=N) в качестве L и точкой N в качестве K. Запоминаем все точки N в массиве.
6. Выходим тогда, когда очередная Lj оказывается начальной прямой L.

Для облегчения восприятия добавлю, что это есть обход точки А по часовой стрелке начиная с ближайшей прямой.