На плоскости заданы N точек. Требуется построить их выпуклую оболочку, т.е. наименьший выпуклый многоугольник, который содержал бы все эти точки.

Алгоритм решения

Найти выпуклую оболочку можно с помощью алгоритма Джарвиса, имеющего асимптотическую оценку времени работы O(N^3).

Сначала выберем из всех заданных точек самую нижнюю, а среди всех таких — самую левую. Назовем эту точку start. Условимся обходить выпуклую оболочку в направлении против часовой стрелки, тогда относительно точки start направление обхода изначально будет задаваться, очевидно, вектором dir = (1, 0). Ясно, что сама точка start входит в выпуклую оболочку, тогда, начиная с нее, будем добавлять в выпуклую оболочку точки до тех пор, пока снова не придем в стартовую. Конфигурацией алгоритма будем считать последнюю рассмотренную точку cur (причем эта точка входит в выпуклую оболочку) и текущее значение вектора dir.