4. Построение выпуклой оболочки. Заворачивание подарка.

Заворачивание подарка = Алгоритм Джарвиса.

Выпуклая оболочка – минимальное выпуклое множество, содержащее все исходные точки, то есть не содержит в себе другого выпуклого множества, содержащего все исходные точки.

Найдем крайнюю левую точку за O(n). Затем найдем луч, который образует минимальный угол с вертикальным лучом, направленным вниз. Далее ту же самую операцию повторим для найденной вершины(найденная вершина есть следующая крайняя точка, докажем: если не все точки лежат справа от луча АВ, то есть точка С внутри угла DAB, чего не может быть т.к. DAB-наименьший) и найденного ребра, и так далее пока не найдем всю оболочку. Время решения - O(n^2).