День 1. Геометрия.2D.advanced

1. Метод двух указателей
1. Две самые дальние точки на плоскости за O(n)
2. Расстояние между выпулкыми непересекающимися многоугольниками за O(n)
3. Общая касательная к многоугольникам за O(n)
4. Прямая, разделяющая многоугольники за O(n)
5. Сумма Минковского за O(n)
6. Поиск расстояния между выпуклыми многоугольниками + проверки их пересечения через сумму Минковского.
2. Выпуклая оболочка
1. QuickHull --- алгоритм, работающий в среднем за O(n) и за O(nlogM) в худшем
2. Мелкман --- выпуклая оболочка многоугольника за O(n)
3. Пересечение
1. Простое пересечение выпуклых многоугольников за O(n²)
2. Пересечение выпуклых многоугольников за O(n)
3. Пересечение n полуплоскостей за O(nlogn) (сортировка + стэк)
4. Задача линейного программирования в 2D за O(n) (нашли одну точку в пересечении полуплоскостей)
5. Пересечение и объединение невыпуклых многоугольников за O(n³)
6. Пересечение и объединение кругов за O(n³)
4. Планарный граф
1. Построение планарного графа, задающего пересечение невыпуклых многоугольников
2. Пересечение и объединение многоугольников и кругов за O(n²logn)
3. Разбиение планарного графа на грани за O(n)
4. Теорема Эйлера. Задача про количество частей плоскости.
5. Алгоритм A* (модификация Дейкстры)
6. Сортировка по углу
1. Нахождение диагоналей невыпуклого многоугольника за O(n²logn)
2. Задача "провести точку на плоскости, обходя выпуклые многоугольные препятствия" за O(n²logn)
3. Задача "провести треугольник" (Лоцман с тимуса). Сумма Минковского.