День 4. Пересечение полуплоскостей (1 января)

  1. [Сережа.М] Пересечение полуплоскостей за O(n2)
    1. Алгоритм, реализация
    2. Пересечение выпуклых многоугольников → пересечение полуплоскостей
    3. Площадь объединения треугольников
  2. [Сережа.K] Пересечение полуплоскостей за O(n)
    1. Простой случай: y=kx+b, первая четверть. Запрос: min y(x).
    2. Решение задачи про точки на прямой через пересечение полуплоскостей
    3. Общий случай, пересечение n полуплоскостей
  3. [Сережа.K] Структуры данных и полуплоскости
    1. Задача "купить прямоугольники максимальной суммы"
    2. Задача про "продукт оптимального веса" (контест, Пети Митричева, 2013.09.02)
    3. Задача про отрезки "даны отрезки в верхней полуплоскости приходит запрос x, нужно говорить min y(x)"
  4. [Сережа.K] Формулировка пересечения полуплоскостей, как задачи линейного программирования