Шестая лекция (геометрия)

1. Многоугольники и полуплоскости
1. Пересечение выпуклых за O(n²)
2. Пересечение невыпуклых за O(n³logn)
3. Пересечение невыпуклых за O(klogn)
4. Пересечение полуплоскостей за O(nlogn) (boundinf box + sort + stack)
2. Метод сканирующей прямой
1. В offline для каждой из m точек, сказать, внутри ли она невыпуклого многоугольника
2. Not read Найти два пересекающихся отрезка за O(nlogn)
3. Not read Найти все пересечения отрезков за O((n+k)logn)
3. Метод двух указателей
1. Общие касательные за O(n)
2. [упражнение] Две самые дальние точки за O(n)
3. [упражнение] Кратчайшее расстояние между выпуклыми многоугольниками за O(n)
4. Погрешность
1. Самый маленький угол между векторами
2. Максимальная координата точки пересечения прямых
3. Вычитание
4. Извлечение корня из нуля
5. Минимально возможный угол между двумя целочисленными векторами
6. Погрешность почти всегда относительная, правильный компаратор вещетсвенных чисел