Астрономическая задача для программистов

[waspagv]

Почему она астрономическая - в самом конце. А сама задача такая.

Вариант 1, простой, но бесполезный.

Дано конечное множество точек на плоскости. Построить выпуклый многоугольник минимальной площади (такой, что его вершинами являются только точки из множества), и найти эту площадь.

Решение, возможно, не самое быстрое, находится сразу. Выбрать

Comments

[2born]

Завис на первом варианте: неужели он обязательно получится выпуклым?

[waspagv]

Должен. По определению выпуклый - это такой, все точки которого лежат по одну сторону от любой прямой, проходящей через две соседние вершины. Способ построения - вращения луча вокруг вершины 1 до первого пересечения с первой попавшейся другой точкой множества, которая станет вершиной 2. Соответственно, все точки множества, в том числе потенциальные будущие вершины, окажутся с одной стороны от прямой 1-2. Ведь если бы нашлась точка множества по другую сторону этой прямой, то при вращении луча мы наткнулись бы на нее раньше, и именно она стала бы вершиной 2.

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

[2born]

А что, не все точки из множества обязаны быть вершинами?

[waspagv]

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