Выпуклые многоугольники (1 декября 2016)

1. Всё за логарифм
1. Проверка "внутри ли точка" (один бинпоиск)
2. Поиск экстремальных точек: Ax + Bx → max (один бинпоиск)
3. Поиск касательной (один бинпоиск, два случая)
4. Пересечение с прямой (три бинпоиска на две точки пересечения, 3log₂n сравнений, оптимальный алгоритм делает как минимум 2log₂n)
5. Ближайшая точка к многоугльнику (доказательство монотонности угла, монотонности производной расстояния)
6. Общая касательная за log²n. Простой случай: верхние выпуклые оболочки точек
7. Общая касательная за log²n. Общий случай: можно свести к простому, выделив самую левую и правую точки, можно найти две ближайшие


2. Динамическая выпуклая оболочка
1. Формулировка задачи. Строим верхнюю часть. Все X различны, т.к. можно повернуть на случайный угол.
2. Общая идея: динамическое дерево отрезков по X, в вершине храним верхнюю выпуклую оболочку (от крайних вершин вниз идут два луча на бесконечность)
3. Пересчёт вершины через детей: общая касательная, split детей, которые хранятся в декартовых деревьях