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

[Цири]

Помогите решить задачу!
Пусть 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.

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

[volvo]

Цири, здесь:

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

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

[Цири]

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

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

Цири, здесь:

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

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

[volvo]

Ну, тогда извини, и решай сама...
Тебе же пытаются помочь, ты же еще и огрызаешься..

Нехорошо.

[Lapp]

Volvo, поскольку речь идет о пересечении прямых, и сказано, что многоугольник минимальный по площади, то ясно, что невыпуклым он быть просто не может. Что касается "много" - то это как получится. Проще всего набросать на бумагу несколько прямых, а потом попроставлять точки в разные псевдослучайные места - ситуация сразу проясняется. Задача составлена вполне толково, вот только с множествами кто-то (или они, или она, я склоняюсь к последнему) прошибся..
Цири, конечно, самомнения не занимать.. Я не буду возражать, если ты сотрешь мой алгоритм. Или скажи, что не возражаешь - я сам сотру. Пусть повторит хотя бы..

Не надо ничего удалять Я пока скрыл твое первое сообщение. Потом откроем опять.

Сообщение отредактировано: volvo - 1.03.2006 15:17

[arhimag]

Есть идея взять все возможные треугольники вычеслитьт их стороны, дальше вычеслить их площадь по формуле Герона а дальше просто посмотреть у какого треугольника будет площадь наименьшая, и вершина его - А и тогда это будет многоугольник с наименьшлей площадью с вершиной в точке А.

[Гость]

Тебе же пытаются помочь, ты же еще и огрызаешься..

Нехорошо.

Необижайся я не огрызаюсь а говорю как есть. Сама непойму что там хотят в этой задаче. Эта задача с методички в которой одни условия задач без комментариев. А по данному предмету у нас предусмотрены только практические занятия без лекционных. Вот таки дела.

Volvo, поскольку речь идет о пересечении прямых, и сказано, что многоугольник минимальный по площади, то ясно, что невыпуклым он быть просто не может. Что касается "много" - то это как получится. Проще всего набросать на бумагу несколько прямых, а потом попроставлять точки в разные псевдослучайные места - ситуация сразу проясняется. Задача составлена вполне толково, вот только с множествами кто-то (или они, или она, я склоняюсь к последнему) прошибся..

Ты прав это она да еще и не одна их две. Надо попробывать твой вариант и подключить к задаче мозг а то он у меня скоро атрафируется.