Решение задачи 12.
Рассмотрим два из возможных алгоритмов.
Вариант 1. Строим выпуклую оболочку данного множества точек (см. задачу 10).
Если все точки множества A лежат на контуре, то задача решена. Если же нет, то ищем точку l с минимальным расстоянием до контура -- пусть это минимальное расстояние до стороны фигуры (u,v) (если таких точек несколько, то берем любую из них), вставляем в контур точку l (вместо контура
... u,v ...
будет
... u,l,v, ...).
Для оставшихся точек повторяем описанную выше процедуру, пока последняя не будет вставлена в контур.
Расстояние от точки до стороны - это либо длина перпендикуляра, опущенного из точки на сторону (если проекция точки попадает на отрезок, см. задачу 4), либо, в противном случае, минимальное из расстояний от точки до концевых точек стороны.
Расстояние от точки z(u,v) до ее проекции на прямую Ax+By+C=0 есть
Вариант 2. Строим выпуклую оболочку V данного множества точек (см. задачу 10).
Если все точки множества A лежат на контуре, то задача решена. Иначе обозначим через A1 все внутренние точки выпуклой оболочки V. Строим для нового множества A1 выпуклую оболочку V1 (контуры V и V1 не пересекаются!).
"Склеиваем" два контура:
Выберем по паре последовательных вершин p,s и p1,s1 на контурах V и V1 соответственно так, чтобы в четырехугольнике с вершинами s,p,p1,s1 не лежало больше никаких других точек контуров V и V1. Разрываем контуры V и V1 (убирая ребра (p,s) и (p1,s1)) и объединяем их (добавляя ребра (p,p1) и (s,s1)).
Если внутри V1 нет внутренних точек, то задача решена, иначе же с внутренними точками V1 проделываем те же самые операции: находим выпуклую оболочку и пары последовательных точек на контурах, разрываем и склеиваем контуры, и т.д., пока не получим, что последняя построенная выпуклая оболочка содержит в себе 0, 1 или 2 точки.
Если точек 0, то задача решена. В противном случае присоединяем точки к ранее образованному контуру так, чтобы фигура осталась многоугольником (можно проводить присоединение, как и в варианте 1).
|
