234
правки
Изменения
→Алгоритм Джарвиса
{{notready}}
= Алгоритм Джарвиса =
По-другому "Заворачивание подарка"
== Описание Алгоритма ==
1) Возьмем самую правую нижнюю точку <tex>p_0</tex> нашего множества. <tex>p_0</tex> лежит в выпуклой оболочке, поэтому добавляем ее в ответ.
2) На каждом следующем шаге для последнего добавленного <tex>p_i</tex> ищем <tex>p_{i + 1}</tex> с максимальным полярным углом относительно <tex>p_i</tex> (Если углы равны, надо сравнивать по расстоянию). Добавляем <tex>p_{i + 1}</tex> в ответ. Если <tex>p_{i + 1} == p_0</tex> , заканчиваем алгоритм.
= Алгоритм Грехэма =
