Площадь объединения прямоугольников

Даны $n$ прямоугольников со сторонами, параллельными осям. Найти площадь их объединения.

Складывать площади нельзя: пересечения посчитаются несколько раз. Формула включений-исключений даёт $2^n$ слагаемых — тоже мимо.

Это первая задача, где сканирующая прямая работает на плоскости, а не на прямой.

Решение через сжатие координат

Возьмём все координаты $x$ всех вертикальных сторон и все координаты $y$ всех горизонтальных. Они разбивают плоскость на сетку из не более чем $(2n-1)^2$ ячеек.

Ключевое: каждая ячейка либо целиком покрыта, либо целиком свободна. Границы покрытия проходят только по линиям сетки — других границ нет.

Значит, достаточно для каждой ячейки проверить, покрыта ли она, и сложить площади покрытых.

vector<long long> xs, ys;
for (auto& r : rects) {
    xs.push_back(r.x1); xs.push_back(r.x2);
    ys.push_back(r.y1); ys.push_back(r.y2);
}
sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());

long long total = 0;
for (size_t i = 0; i + 1 < xs.size(); i++)
    for (size_t j = 0; j + 1 < ys.size(); j++) {
        bool covered = false;
        for (auto& r : rects)
            if (r.x1 <= xs[i] && xs[i+1] <= r.x2 && r.y1 <= ys[j] && ys[j+1] <= r.y2) {
                covered = true;
                break;
            }
        if (covered) total += (xs[i+1] - xs[i]) * (ys[j+1] - ys[j]);
    }

Проверено: на двадцати тысячах случайных наборов до пяти прямоугольников результат совпал с прямым подсчётом покрытых единичных клеток.

Проверять ячейку достаточно по любой её внутренней точке — например, по левому нижнему углу с полуоткрытыми границами, как в коде.

Сложность

$O(n^3)$: до $2n$ линий по каждой оси, значит до $4n^2$ ячеек, и на каждую проход по $n$ прямоугольникам.

При $n$ до 200 это проходит. Для больших $n$ есть два улучшения.

До $O(n^2)$. Ведём сканирующую прямую по $x$: для каждой вертикальной полосы между соседними $x$-линиями считаем длину покрытия по $y$ обычным объединением отрезков. Полос $O(n)$, каждая стоит $O(n \log n)$.

До $O(n \log n)$. То же, но длина покрытия по $y$ поддерживается деревом отрезков с добавлением и удалением. Классическое решение, но заметно сложнее.

Практический совет: начинайте с $O(n^3)$. Он пишется за десять минут, отлаживается моментально и часто проходит. Когда решение уже работает, его легко ускорить, а заодно есть с чем сверять.

Что ещё считается так же

Периметр объединения. Считается той же сканирующей прямой, но следят не за длиной покрытия, а за её изменением при переходе через каждую вертикальную линию: приращение длины покрытия даёт вертикальный вклад в периметр, а число «кусков» покрытия — горизонтальный.

Число связных компонент объединения. Уже сложнее и обычно требует системы непересекающихся множеств.

Площадь, покрытая ровно $k$ прямоугольниками. Та же сетка, но вместо флага «покрыта» считаем, сколько прямоугольников накрывают ячейку.

Все три задачи решаются тем же сжатием координат и тем же двойным циклом — меняется только то, что мы считаем внутри.

Про сжатие координат

Приём здесь тот же, что в одномерном случае: координаты до $10^9$, но различных значений не больше $2n$.

Разница в том, что нас интересуют промежутки между значениями, а не сами значения. Поэтому в цикле стоит i + 1 < xs.size(), а площадь ячейки считается как произведение разностей, а не как единица.

Это общее место в двумерных задачах, и путаница «индекс против промежутка» — главный источник ошибок здесь. Если ответ отличается ровно на площадь одной полосы, ищите ошибку именно тут.