Изменения

Перейти к: навигация, поиск
Описание Алгоритма
[[File:Graham2.png|thumb|400px|Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки <tex>p</tex> последовательно убираем из оболочки точки с <tex>i+3</tex>-ей до <tex>i+1</tex>-ой]]
1)Находим самую правую нижнюю точку множества <tex>p_0</tex>нашего множества с самой маленькой у-координатой (если таких несколько, берем самую правую из них), добавляем в ответ.
2)Сортируем все остальные точки {{Acronym|по полярному углу относительно <tex>p_0</tex>|Сортировка с компаратором "Предикат поворота"}}.
3)Добавляем в ответ <tex>p_1</tex> - самую первую из отсортированных точек.
5)Добавляем в оболочку <tex>t</tex>.
6)Делаем п.5, пока не закончатся точки.
== Корректность ==
Анонимный участник

Навигация