Изменения

Перейти к: навигация, поиск
м
Нет описания правки
== Левая и правая выпуклые оболочки ==
Определим левую (правую) выпуклую оболочку множества точек <tex>P</tex>, как выпуклую оболочку множества <tex>P \cup \{\infty_+\}</tex> <tex>(P \cup \{\infty_-\})</tex>, где <tex>\infty_- = (-\infty, 0), \infty_+ = (+\infty, 0)</tex>. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек. Далее будем Будем рассматривать только динамическое поддержание левой оболочки (далее, для краткости, будем называть её просто выпуклой оболочкой). Заметим также, что точки вдоль выпуклой оболочки отсортированы по ординате.
{|border="0" cellpadding="5" width=30% align=center
get_hull(answer, v.right, max(l, b), r)
Левый конец моста добавляется только если ответ пустой, иначе он уже был добавлен как правый конец другого моста. Чтобы получить выпуклую оболочку нужно вызвать get_hull([], root, <tex>infty_-\infty</tex>, <tex>infty_+\infty</tex>).
=== Принадлежность точки выпуклой оболочке ===
73
правки

Навигация