Геометрия

1. Пересечение полуплоскостей
1. За O(N²)
2. За O(NlogN)
3. Борьба с хвостами путем выделения цикла. Проход по массиву полуплоскостей 2 раза.
2. Площадь объединения (пересечения)
1. Прямоугольников за O(N³)
2. Трапеций (домов, задача I) за O(N³)
3. Кругов за O(N³) (каждый круг = 3 точки)

Метод ScanLine-а

1. ScanRay
1. Задача "освещение" про площадь освещаемой части невыпуклого многоугольника
2. Задача "выстрелы по стенам". Вторая коордианата = время.
2. Про отрезки
1. Сортировка непересекающихся отрезков за O(NlogN).
2. Пересекаются ли N отрезков за O(NlogN).
3. Площадь объединения прямоугольников
1. O(N²logN)
2. O(N²)
3. Not read O(NlogN)

изоморфизм деревьев.

1. За O(NlogN) хэшами для подвешенных деревьев.
2. За O(N) хэшами
3. Случай не подвешенных деревьев, асимптотика та же.
4. Задача про разбиение K деревьев на классы эквивалентности (за то же время)
5. изоморфизм графов.
1. Степени вершин
2. итерированный хэш за O(N³)
3. Хэширование дополнительной информации, матрица смежности, характеристический многочлен.