ЛКШ 2016. Группа A. День 11. Геометрия-1.

  1. Python
    1. base knowlege
    2. tkinter, visualizer
  2. 2D convex hull
    1. Алгоритм Andrew'79: отдельно строим верхнюю и нижнюю часть. Преимущества.
    2. Jarvis. Заворачиванием подарка за O(nk).
  3. Пересечение полуплоскостей
    1. Bounding box
    2. Пересечение полуплоскостей за O(n2)
    3. Простой случай: y > kx + b (k > 0)
    4. Пересечение полуплоскостей в общем случае: отдельно строим и пересекаем верхнюю и нижнюю части
    5. Пересечение полуплоскостей в общем случае: удваиваем и выделяем цикл
    6. Двойственность с выпуклой оболочкой: (x, y) ↔ (k, -b)
    7. Примеры использования: пересечение полуплоскостей за O(nk), медиана углов n2 прямых построенных по n точкам