$ ЛКШ 2018, 4-й день, 2D геометрия (Илья Подуременных)

# Два указателя, задачи решающиеся за O(n)
## 2 самые дальние точки (калиперы) - первую точку нашли, дальше двигаем на меньший угол
## Общая касательная (2 указателя) - нашли от одной точки, а потом двигаем указатель

<br>
# Бинпоиски, задачирешающиеся за полилог
## Локализация точки (1 бинпоиск) - 2 способа (из вершины, из центра)
## Расстояние от точки до прямой
## Опорная прямая, 2 штуки (2 бинпоиск) - бипоиск по углу -- 2 способа
## Самая дальная по направлению точка (ax + by &rarr; max) (1 бинпоиск) - перейти к опорной (связь с проекцией)
## Пересечение прямой с многоугольником (3 бинпоиска) - 1 точку взяли, 2-ую бинпоиском, между ними 2 бинпоиска
## Касательные из точки к многоугольнику (2 бинпоиска) - взяли любую точку и один бинпоиск по векторному произведению "та самая функция" 
## Ближайшая (3 бинпоиск) - нашли 2 касательные и бинпоиск между ними
## Общая касательная - зафиксировали касательную, бинпоиск относительно неё
## Расстояние между многоугольгиками - построили общие касательные, бинпоиск между ними

<br> 
# Сумма Минковского 
## Определение, построение за O(n+m)
## Path finding для многоугольника с многоугольными препятствиями, асимптотический оптимайз
## Проверить, пересекаются ли два многоугольника за O(n+m), найти расстояние за O(n+m)

<br>
# Динамическая выпуклая оболочка
## Точки только добавляются &rArr; set, все наши методы за O(logn) всё ещё работают (заменили бинпоиск на спуск по дереву)
## И добавляются, и удаляются &rArr; дерево отрезков по X, пересчёт через детей общей касательной и персистентным treap
