Геометрия

  1. [Сережа.K] Основы
    1. Векторное и скаляроное произведение. Расстояние от круга до квадрата.
    2. Погрешность
    3. Выпуклая оболочка за O(nlogn)
    4. Проверка, лежит ли точка в многоугольнике за O(n)
    5. Ориентация многоугольника по часов стрелке (считаем площадь, reverse)
  2. [Сережа.K] ScanLine
    1. Проверить, есть ли пересечение отрезков за nlogn
    2. Найти все пересечения отрезков за (n+k)logn
    3. Посчитать, какие точки видимы из данной
    4. Посчитать освещенную площадь
    5. Проверка в Offline для каждой точки, лежит ли она в многоугольнике.
  3. [Сережа.М] Два указателя
    1. [skipped] Общая касательная для двух выпуклых многоугольников за O(n)
    2. Расстояние между двумя выпуклыми непересекающимися многоугольниками за O(n)
    3. Максимальное расстояние между точками в 2D за O(ConvexHull + n)
    4. Треугольник максимальной площади за O(n2). А еще бывает O(ConvexHull + n)!
    5. Четырехугольник максимальной площади за O(n2)
    6. [skipped] Сумма Минковского за O(n)
    7. Количество четверок точек, образующих выпуклый четырехугольник за O(n2logn)
  4. [skipped] [Сережа.М] За log!
    1. [skipped] Опорные прямые
    2. [skipped] Касательные из точки к многоугольнику (произвольному, построим выпуклую оболочку)
    3. [skipped] Проверка, внутри ли точка выпуклого многоугольника в Online