74
правки
Изменения
Нет описания правки
Пусть дано множество точек <tex>S</tex>, изначально пустое, и последовательность точек <tex>\{p_i\}^n_{i = 1}</tex>, которые последовательно добавляются или удаляются из <tex>S</tex> (естественно, точка может быть удалена, если она уже принадлежит <tex>S</tex>). Требуется динамически поддерживать выпуклую оболочку <tex>S</tex>.
=== Получение выпуклой оболочки ===
Научимся восстанавливать выпуклую оболочку по дереву, описанному выше. Для этого рассмотрим более общую задачу: для данной вершины дерева <tex>v</tex> и отрезка <tex>[l, r]</tex> найти выпуклую оболочку точек поддерева с корнем в <tex>v</tex>, ординаты которых лежат в этом отрезке. Это можно сделать следующим обходом:
get_hull(answer, v, l, r)
'''if''' (v.leaf)
'''return'''
a = v.bridge.left.y
b = v.bridge.right.y
'''if''' (l < a)
get_hull(answer, v.left, l, min(a, r))
'''if''' (l <= a and b <= r)
'''if''' (answer.empty())
answer = answer ++ v.bridge.left
answer = answer ++ v.bridge.right
'''if''' (b < r)
get_hull(answer, v.right, max(l, b), r)
Левый конец моста добавляется только если ответ пустой, иначе он уже был добавлен как правый конец другого моста. Чтобы получить выпуклую оболочку нужно вызвать get_hull([], root, <tex>infty_-</tex>, <tex>infty_+</tex>).
=== Принадлежность точки выпуклой оболочке ===
