:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » Выпуклая оболочка » Gift Wrapping
  Gift Wrapping



Перевод: Кантор И.
e-mail: algolist@mail.ru
web: iliakan@gmail.com

Этот алгоритм обводит точки линией, 'заворачивая' в выпуклую оболочку. На рисунке ниже дана подробная иллюстрация его действия.

     Находим нижнюю-правую точку. Пусть это - i(0). i=i(0).
     Повторять :
        - Для каждого j != i вычисляем точку с наименьшим 
                углом от предыдущей стороны 
                ( для второй точки - от горизонтали ). 
                Если есть две таких - берем ту, 
                до которой расстояние больше. Пусть ее номер - k.
        - Выводим сторону из точек с номерами i и k. i = k.
     пока i не станет равно i(0).

Исходник собственно функции - simple_convex() в geom.c. Программа компилируется и работает под GCC 2.95. Скачатьzip.