11. Динамическое построение выпуклой оболочки.

Динамическое построение выпуклой оболочки (точки постоянно добавляются).

Динамическое поддержание выпуклой оболочки (точки постоянно добавляются и удаляются).

Вначале определим за O(logn) лежит ли точка внутри выпуклой оболочки. На входе имеем упорядоченное по углу множество лучей; найдем за O(logn) угол, в который попала точка; за константу определяем справа она или слева от соответствующего ребра. Если слева (при обходе против часовой стрелки), то задача решена – выпуклую оболочку не перестраиваем.

Найдем опорные лучи, за константу определим ближнюю цепь (по углу между смежными к опорной вершине ребрами и лучом из опорной точки в т.P) и поменяем ссылки на точки.