234
правки
Изменения
→Алгоритм Грэхема
== Описание Алгоритма ==
[[File:TempGraham2.gifpng|thumb|250px400px|Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки <tex>p</tex> последовательно убираем из оболочки точки с <tex>i+3</tex>-ей до <tex>i+1</tex>-ой]]
1)Находим самую правую нижнюю точку множества <tex>p_0</tex>, добавляем в ответ.
2)Сортируем все остальные точки по полярному углу относительно <tex>p_0</tex>.
3)Добавляем в ответ <tex>p_1</tex> - самую первую из отсортированных точек.
4)Берем следующую по счету точку в массиве <tex>t</tex>. Пока <tex>t</tex> и две последних точке точки в ответе текущей оболочке <tex>p_i</tex> и <tex>p_{i-1}</tex> образуют неправый поворот, удаляем из ответа последнюю точкуоболочки <tex>p_i</tex>. 5)Добавляем в оболочку <tex>t</tex>. 6)Делаем п.45, пока не закончатся точки.
== Корректность ==
== Псевдокод ==
== Сложность ==
Сортировка точек занимает <tex>O(n \log n)</tex> времени. При обходе каждая точка добавляется в ответ не более одного раза, поэтому сложность этой части - <tex>O(n)</tex>. Суммарное время - <tex>O(n \log n)</tex>.
= Алгоритм =
