Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Геометрия >> Номер 12

[Назад]    [Содержание ]    [Вперед]

  


Номер 12


  Условие: Номер 12


Задача 12. N точек на плоскости заданы своими координатами. Найти порядок, в котором можно соединить эти точки, чтобы получился N-угольник (т.е. не было бы пересечений сторон).

  Решение задачи: Номер 12


Решение задачи 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).

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017