Решение задачи 11.
Предположим, что мы построили искомый выпуклый многоугольник. Если какая-то точка a (из данного в условии набора S, состоящего из k точек) лежит на стороне многоугольника, то мы считаем ее новой вершиной этого многоугольника. Мы можем считать, что все вершины данного многоугольника есть точки набора S (если это не так, и между двумя точками a и b набора S лежит одна или несколько "посторонних" вершин, то мы можем их отбросить и считать, что a и b - две последовательные вершины контура. Многоугольник при этом у нас остается выпуклым (отрезок [a,b] делит фигуру на два выпуклых многоугольника), а так как на контуре между a и b не лежало ни одной точки из S, то многоугольник все еще удовлетворяет требованиям задачи).
Итак, в качестве решения задачи мы получили выпуклую оболочку множества S (о построении ее см. задачу 10).
Если построенная выпуклая оболочка такова, что каждая точка S является ее вершиной (или лежит на стороне), то задача решена, иначе решения не существует.
|
