Изменения

Перейти к: навигация, поиск
Нет описания правки
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>
 
Пусть дано множество точек <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>).
=== Принадлежность точки выпуклой оболочке ===
74
правки

Навигация