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

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


2. Бинпоиски, задачи решающиеся за полилог
1. Локализация точки (1 бинпоиск) - 2 способа (из вершины, из центра)
2. Расстояние от точки до прямой
3. Опорная прямая, 2 штуки (2 бинпоиск) - бипоиск по углу − 2 способа
4. Самая дальная по направлению точка (ax + by → max) (1 бинпоиск) - перейти к опорной (связь с проекцией)
5. Пересечение прямой с многоугольником (3 бинпоиска) - 1 точку взяли, 2-ую бинпоиском, между ними 2 бинпоиска
6. Касательные из точки к многоугольнику (2 бинпоиска) - взяли любую точку и один бинпоиск по векторному произведению "та самая функция"
7. Ближайшая (3 бинпоиск) - нашли 2 касательные и бинпоиск между ними
8. Общая касательная - зафиксировали касательную, бинпоиск относительно неё
9. Расстояние между многоугольгиками - построили общие касательные, бинпоиск между ними


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


4. Динамическая выпуклая оболочка
1. Точки только добавляются ⇒ set, все наши методы за O(logn) всё ещё работают (заменили бинпоиск на спуск по дереву)
2. И добавляются, и удаляются ⇒ дерево отрезков по X, пересчёт через детей общей касательной и персистентным treap