Алгоритмическое задание - Найти многоугольник минимального периметра для заданного набора точек

[polarity]

Здраствуйте.

Дано N точек на плоскости. Найти многоугольник максимального периметра с непересекающимися сторонами, содержащий внутри себя все заданные точки. Компонент PaintBox служит для графического представления данных.

Было бы очень здорово, если кто-нибудь помог с задачей

[Serge_Bliznykov]

лмбо условие неправильно сформулировано (пропущена какая-та часть описания данного многоугольника. ну, например, вершинами должны являться только заданные точки),
либо задача не имеет решения.

очевидно, что многоугольник с максимальным периметром должен начинаться (левый нижний угол) где-то в районе ]-бесконечность, -бесконечность[ и заканчиваться (правый верхний угол) где-то в районе ]+бесконечность, +бесконечность[

...

[Аватар]

Похоже нужно найти многоугольник минимального периметра

[D-mon]

Хотелось бы уточнить:
1. Дано N точек на плоскости. Точки заранее известны(их коордтнаты)?
2. "содержащий внутри себя все заданные точки" - как это понять? Надо с клавиатуры ввести координаты точек, которые должны находиться внутри найденого многоугольника???

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

[Serge_Bliznykov]

я на 90% уверен, что Аватар прав. Нужно найти многоугольник с минимальным периметром.

D-mon, да. Есть N точек, заданных своими координатами.
И какая разница, откуда они берутся?
Генерятся случайным образом, вводятся с клавиатуры или читаются из файла...

По поводу того, что задача непростая, согласен. Тут и один многоугольник построить досточно муторно, а ещё и перебрать ВСЕ варианты... (особенно если про вершины многоугольника в условии нет оговорок)..


Подобные задачи - это уже олимпийский уровень...


Кстати, вполне могу ошибится, но мне кажется, что минимальным периметром будет обладать всё таки многоугольник,
построенный на заданных точках (разумеется не обязательно всех, а только нужных)...
но расписать алгоритм полностью я не готов...

[Аватар]

Подобные задачи - это уже олимпийский уровень...

Сомневаюсь. На бумаге это выглядит так: находишь самую верхнюю точку (если их несколько - то любую из них). Начало луча в эту точку, направление - горизонтально и вправо, вращение по часовой стрелке до первого пересечения с другой точкой, которая и будет вторым концом отрезка. Если таких точек несколько - то выбирать самую дальнюю. Начало луча в эту точку, направление - в продолжение предыдущего отрезка, вращаем по часовой стрелке как в предыдущем случае. И т.д. Задача имеет решение для точек больше 2 и не менее 3 из них лежит не на одной прямой. И это решение единственное

[polarity]

Как я понял, несколько точек рандомно появляются на форме и строится многоугольник (скорее всего вы правы - минимального периметра).
Вот с таким условием подскажите что-нибудь - с графикой вообще не очень, прямоугольники полчаса рисую

[Serge_Bliznykov]

Сообщение от Аватар

Сомневаюсь.

зря... )

отсюда:
Вихтенко Эллина Михайловна
ГЕОМЕТРИЧЕСКИЕ ЗАДАЧИ В ОЛИМПИАДАХ ПО ПРОГРАММИРОВАНИЮ (Статья по информатике из журнала МИФ-2 №2 за 2005 год)

Задача 2 «Здесь будет город-сад». Жители одного дома города Х решили высадить у себя во дворе несколько деревьев. Так как жильцы не смогли договориться, как должны быть расположены посадки, то каждый посадил дерево в том месте двора, где ему захотелось. После проведения посадок полученный сад решили обнести забором. Но пока доски не привезли, деревья обвязали одной длинной веревкой.
Исходная информация: N – количество деревьев в саду, (xi, yi) – координаты деревьев, i=1,2, …, N. Так как были высажены молодые саженцы, то их толщиной можно пренебречь.
Требуется определить, к каким из посаженных деревьев надо привязать веревку так, чтобы все деревья оказались внутри обнесенной зоны, а длина веревки была минимальная.
.....

ну и тут ещё: статья "Вычислительная геометрия на плоскости" Е.В. Андреева, Ю.Е. Егоров.

На бумаге это выглядит так: находишь самую верхнюю точку (если их несколько - то любую из них). Начало луча в эту точку...

угу. в вышеприведённой статье чуть другой алгоритм. но идея такая же..
Проблема в том, что то, что ручками на бумаге делается за секунду, в коде на ЯП записывается ой как не просто!!

[D-mon]

Сообщение от Serge_Bliznykov

D-mon, да. Есть N точек, заданных своими координатами.
И какая разница, откуда они берутся?
Генерятся случайным образом, вводятся с клавиатуры или читаются из файла...

Дано N точек на плоскости.

- эти понятно что не вводятся в ручную...

содержащий внутри себя все заданные точки.

- а эти точки, не исключено, что надо вести самостоятельно.

[polarity]

Сообщение от D-mon

- эти понятно что не вводятся в ручную...
- а эти точки, не исключено, что надо вести самостоятельно.

Пусть все точки будут.