Алгоритмическая задача про прямоугольники на плоскости
Как можно решать такую вот задачу: на плоскости заданы n прямоугольников со сторонами, параллельными осям координат. И нужно определить суммарную площадь регионов, покрытых нечётным числом прямоугольников. За асимптотику O(n log n).
Ответы (2 шт):
Автор решения: MBo
→ Ссылка
Использовать метод сканирующей прямой (sweep line)
(случайная ссылка, ыщо одна),
модифицировав подход для нечетного покрытия.
Автор решения: Владислав Никишкин
→ Ссылка
Дерево отрезков (ДО) - динамическая структура данных, которая отвечает на запросы на отрезках.
ДО + сканлайн:
- сжимаешь координаты, если надо
- сканлайн будет итерироваться по оси ординат
- заводишь вектор длиной оси абсцисс (со сжатыми кордами). i-ый элемент - количество прямоугольников, покрывающих i-ую координату
- на каждой итерации с помощью ДО обновляешь этот вектор + считаешь количество ноликов (опять же с помощью ДО)