9. Построение выпуклой оболочки. Метод Грехема.

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

Алгоритм Грэхема. Найдем внутреннюю точку Р(берем любые три исходных и находим центр вписанной окружности). Из точки Р проводим лучи во все исходные точки, присваиваем точкам номера по принципу увеличения угла поворота луча.

Если из точки "3" произошел правый поворот, то ее выбрасываем и рассматриваем угол 1 2-2 4(шаг назад). В конце проверяем и первую точку или заранее выбираем крайнюю слева(справа, сверху, снизу). Шагов назад не более n, так как при каждом шаге назад одна из точек более не рассматривается. Общее время обхода всех точек O(n). Решение задачи построения оболочки O(nlogn).