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

[Цири]

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

Сообщение отредактировано: Цири - 28.02.2006 7: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.

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

[Цири]

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

Методичку из которой я взяла задачу составляли ИДИОТЫ. И эта задача как там написано на множества и предполагаю что речь идет о множестве прямых. Такой алгоритм я и сама составить могу, а что - то поближе к Паскалю можно?

Цири, здесь:

что понимается под "МНОГОугольником"? Трех? Четырех? N-угольник? Выпуклость его имеет значение?

НЕЗНАЮ. Как написано в методичке я так и написала. А если бы в голове хоть какие то варианты по этой задачи были я ее сама бы сделала.