234
правки
Изменения
→Алгоритм Грэхема
= Алгоритм Грэхема =
Алгоритм заключается в том, что мы ищем точки оболочки последовательно, используя стек.
== Описание Алгоритма ==
3)Добавляем в ответ <tex>p_1</tex> - самую первую из отсортированных точек.
4)Берем следующую по счету точку <tex>t</tex>. Пока <tex>t</tex> и две последних точки в текущей оболочке <tex>p_i</tex> и <tex>p_{i-1}</tex> образуют неправый поворот(вектора <tex>p_i t</tex> и <tex>p_{i-1} p_i</tex>), удаляем из оболочки <tex>p_i</tex>.
5)Добавляем в оболочку <tex>t</tex>.