Изменения
→Ссылки
k = 2
for p = 3..n
while S[k - 1], S[k], S[p] has non-right orientationand k > 1
k--
swap(S[p], S[k + 1]) k++
return k + 1
== Сложность ==
Сортировка точек занимает <tex>O(n \log n)</tex> времени. При обходе каждая точка добавляется в ответ не более одного раза, поэтому сложность двух обходов - <tex> 2 \cdot O(n)</tex>. Суммарное время - <tex>O(n \log n)</tex>. Также можно отметить тот факт, что Эндрю в целом работает быстрее чем ДжарвисГрэхем, так как использует всего <tex>O(n)</tex> поворотов, в то время как Грехем Грэхем использует <tex>O(n \log n)</tex> поворотов.
== Ссылки ==
* [http://en.wikipedia.org/wiki/Graham_scan#Notes Одно предложение о нем]
* [https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain Имплементация на 13 языках]
= Алгоритм Чена =
== Реализация ==
Заметим, что длина высоты, опущенная из точки <tex>t</tex> на отрезок <tex>ab</tex>, пропорциональна векторному произведению <tex>[bt \cdot ba]</tex>, поэтому для сравнения можно использовать именно это. Векторное произведение эквивалентно предикату поворота, поэтому можно так же использовать и его.
== Псевдокод ==
