База, которая необходима для понимания лекции

1. Геометрия
1. Пересечение двух прямых
2. Пересечение двух отрезков
3. Площадь треугольника
4. Площадь многоугольника
5. Ориентация многоугольника
6. Разбиение прямой точек на три множества (срава, слева, лежащие на)
2. Численные методы.
1. Двоичный поиск. Корень многочлена нечетной степени.
2. Троичный поиск. Локальный минимум любой функции за O(logN).
1. Принцип работы: Точки A, B, C образуют невыпуклость, берем точки X, Y, делаем один из трех переходов.
2. Задача: timus : 1256 (Про "посетить" 2 окружности)
3. Не работает? Разобьем на 100 более маленьких кусков, на каждом троичный поиск.

Алгоритмы работы с выпуклыми многоугольниками

1. Пересечения.
1. Пересечение многоугольника прямой за O(N).
2. Пересечение двух выпуклых многоугольников за O(N²).
2. Разбиения.
1. Разбиение прямой на 2 равные по площади части за O(N).
2. Разбиение прямой на 2 равные по периметру части за O(N).
3. Разбиение прямой на 2 равные по периметру части минимальной по длине хордой (троичный поиск)
4. Разбиение прямой на 2 равные по площади и по периметру части за O(NlogMax).
5. Разбиение двумя перпендикулярными прямыми на 4 равные части.
3. logN
1. Нахождение точки, экстремальной по направлению, за O(logN).
2. Нахождение точек пересечения с прямой за O(logN).
3. Построение общих касательных за O(logN).
4. Проверка - внутри, или снаружи лежит данная точка за O(logN).
4. logN Hard.
1. Нахождение расстояния до многоугольника за O(logN). Передний фронт.
2. Невозможность решать задачу "max расстояние".
3. Хранение многоугольника в декартовом дереве. Пересечение прямой за O(log²N).
4. Оптимизация предыдущей идеи до O(logN). Бинпоиск по массиву = Find в дереве поиска.
5. Метод двух указателей.
1. Построение общей касательной для двух многоугольников за O(N);
2. Нахождение ближайшей точки за O(N).
3. Нахождение двух самых дальних точек в множестве за O(N).