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

Как найти площадь прямоугольников с учётом пересечений (объединение прямоугольников) за O(n log n)

Задача: На плоскости есть много прямоугольников. Их стороны параллельны осям координат. Нужно посчитать занимаемую ими площадь. Так же нужно учитывать то что они пересекаются. И всё бы хорошо, только прямоугольников целых 100000, а их координаты достигают 10^14 (ага, и размеры ~10^18)! Я придумал только такое решение:
Используем метод сканирующей прямой. Сортируем по x все вертикальные стороны. Проходимся по ним, и соответственно формула при переходе прямой такая:
S_new = DELTA_X * active_ys;
Где DELTA_X — насколько переместилась сканирующая прямая, а active_ys — суммарная высота пересекающих линию прямоугольников.
И проблема как раз таки в вычислении этого active_ys. Можно сохранять все высоты прямоугольников как отрезки, и потом их складывать с учётом пересечений, но у меня это получается только за O(Y) (где Y — кол-во отрезков), и сложность всего алгоритма получается O(NY), а т.к. в худшем случае Y = N, то выходит O(N^2), что разумеется очень плохо. Можно было бы хранить все точки по y, но учитывая ограничения по координатам (10^14) ни в какую память это не влезет. Еще была идея хранить в дереве отрезков все эти отрезки, но непонятно как их суммировать, т.к. они ведь могут и не пересекаться, и задача по сути вернётся к исходной. К тому же эти отрезки надо ещё и удалять. Может кто-то знает как можно решить эту задачку хотя бы за O(n log n)?

возможно глупая идея, потому просто комментом напишу. У вас же проблема в том, что прямоугольники пересаются, иначе можно было бы просто все плошади сложить, так? А что если отсортировать все прямоугольники, идти слева направо, находить все пересекающиеся прямоугольники и делить их на более мелкие прямоугольники, но которые уже не пересекаются? Типа если 2 прямоугольника пересекаются, то убрать их и вместо них добавить прямоугольники (до 5 штук), но которые уже не пересекаются? Интуиция говорит, что это вроде можно за логарифм сделать, и потом за линию сложить все площади.

возможно, но мне кажется что не сработает, т.к. уже разделённые прямоугольники могут опять пересекаться с чем-нибудь, значит и для них тоже надо проводить проверку, и может так выйти что можно эти прямоугольники почти до бесконечности делить.

Заметаете прямой. Статус — дерево отрезков, которое хранит минимум числа покрытий (прямоугольниками) для точки. Такое дерево обновляется за логарифм при добалении/убавлении прямоугольника. Всего будет nlogn.

для точки — если имеете ввиду каждую y-точку на прямой, то этих точек у меня примерно 10^18*2, не думаю что влезет в оперативку.

Все горизонтальные стороны прямоугольников сортируете. Получаете 2 * 10^5 — 1 отрезков на вертикальной прямой. Собираете их в дерево. При заметании вертикальной прямой добавление/удаление прямоугольника влияет на отрезки целиком, не на отдельные точки.

Источник

Сканирующая прямая

Метод сканирующей прямой (англ. scanline) заключается в сортировке точек на координатной прямой либо каких-то абстрактных «событий» по какому-то признаку и последующему проходу по ним.

Он часто используется для решения задач на структуры данных, когда все запросы известны заранее, а также в геометрии для нахождения объединений фигур.

#Точка, покрытая наибольшим количеством отрезков

Задача. Дан набор из $n$ отрезков на прямой, заданных координатами начал и концов $[l_i, r_i]$. Требуется найти любую точку на прямой, покрытую наибольшим количеством отрезков.

Рассмотрим функцию $f(x)$, равную числу отрезков, покрывающих точку $x$. Понятно, что каждую точку этой функции мы проверить не можем.

Назовем интересными те точки, в которых происходит смена количества отрезков, которыми она покрыта. Так как смена ответа может происходить только в интересной точке, то максимум достигается также в какой-то из интересных точек. Отсюда сразу следует решение за $O(n^2)$: просто перебрать все интересные точки (это будут концы заданных отрезков) и проверить для каждой по отдельности ответ.

Это решение можно улучшить. Отсортируем интересные точки по возрастанию координаты и пройдем по ним слева направо, поддерживая количество отрезков cnt , которые покрывают данную точку. Если в данной точке начинается отрезок, то надо увеличить cnt на единицу, а если заканчивается, то уменьшить. После этого пробуем обновить ответ на задачу текущим значением cnt .

Как такое писать: нужно представить интересные точки в виде структур с полями «координата» и «тип» (начало / конец) и отсортировать со своим компаратором. Удобно начало отрезка обозначать +1, а конец -1, чтобы просто прибавлять к cnt это значение и не разбивать на случаи.

Единственный нюанс — если координаты двух точек совпали, чтобы получить правильный ответ, сначала надо рассмотреть все начала отрезков, а только потом концы (чтобы при обновлении ответа в этой координате учлись и правые, и левые граничные отрезки).

  Такое решение работает за $O(n \log n)$ на сортировку. Если координаты небольшие, то от логарифма можно избавиться, если создать vector событий для каждой различной координаты и просто итерироваться по всем целочисленным координатам и событиям в них. Также всегда хорошей идеей будет сжать координаты.

Рассмотрим теперь несколько смежных задач.

#Длина объединения отрезков

Задача. Дан набор из $n$ отрезков на прямой, заданных координатами начал и концов $[l_i, r_i]$. Требуется найти суммарную длину их объединения.

Как и в прошлой задаче, отсортируем все интересные точки и при проходе будем поддерживать число отрезков, покрывающих текущую точку. Если оно больше 0, то отрезок, который мы прошли с прошлой рассмотренной точки, принадлежит объединению, и его длину нужно прибавить к ответу:

#Скольким отрезкам принадлежит точка

Пусть теперь надо для $q$ точек (не обязательно являющихся концами отрезков) ответить на вопрос: скольким отрезкам принадлежит данная точка?

Воспользуемся следующим приемом: сразу считаем все запросы и сохраним их, чтобы потом ответить на все сразу. Добавим точки запросов как события с новым типом 0, который будет означать, что в этой точке надо ответить на запрос, и отдельным полем для номера запроса.

Теперь аналогично отсортируем точки интереса и пройдем по ним слева направо, поддерживая cnt и отвечая на запросы, когда их встретим.

#Количество пересекающихся отрезков

Задача. Дан набор из $n$ отрезков на прямой, заданных координатами начал и концов $[l_i, r_i]$. Требуется для каждого отрезка сказать, с каким количеством отрезков он пересекается (в частности, он может иметь одну общую точку или быть вложенным).

Вместо того, чтобы для каждого отрезка считать количество отрезков, с которыми он пересекается, посчитаем количество отрезков, с которыми он не пересекается, и вычтем это число из $(n-1)$.

1. Какой-то отрезок закончился в координате $r_i$.
2. Какой-то отрезок с таким-то индексом начался в координате $l_j$.

Теперь нам достаточно пройтись по этим событиям слева направо, поддерживая количество встреченных событий первого типа и вычитая его из ячейки ответа для событий второго типа.

Аналогично пройдемся справа налево, находя отрезки, лежащие строго справа. Итоговое время работы будет $O(n \log n)$ на сортировку.

#Сумма на прямоугольнике

Перейдем к двумерному сканлайну.

Задача. Даны $n$ точек на плоскости. Требуется ответить на $m$ запросов количества точек на прямоугольнике.

Во-первых, сожмем все координаты (и точек, и запросов): будем считать, что они все порядка $O(n + m)$.

Теперь разобьём каждый запрос на два запроса суммы на префиксах: сумма на прямоугольнике $[x_1, x_2] \times [y_1, y_2]$ равна сумме на прямоугольнике $[0, x_2] \times [y_1, y_2]$ минус сумме на прямоугольнике $[0, x_1] \times [y_1, y_2]$.

Создадим дерево отрезков для суммы и массив ans для ответов на запросы. Теперь будем проходиться в порядке увеличения по всем интересным $x$ — координатам точек и правых границ префиксных запросов — и обрабатывать события трёх типов:

1. Если мы встретили точку, то добавляем единицу к ячейке $y$ в дереве отрезков.
2. Если мы встретили «левый» запрос префиксной суммы, то посчитаем через дерево отрезков сумму на отрезке $[y_1, y_2]$ и вычтем его из ячейки ответа.
3. Если мы встретили «правый» запрос, то аналогично прибавим сумму на $[y_1, y_2]$ к ячейке ответа.

Таким образом, мы решим задачу в оффлайн за $O(n \log n)$: сжатие координат / сортировка плюс $O(n)$ запросов к дереву отрезков (или любой другой структуре для динамической суммы).

Сумма на прямоугольнике как вспомогательная подзадача также часто используется в задачах на инверсии в перестановках и запросы на поддеревьях.

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

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

Вдохновляясь предыдущим подходом, можно создать два типа событий:

1. прямоугольник с $y$-координатами от $y_1$ до $y_2$ начинается в точке $x_1$;
2. прямоугольник с $y$-координатами от $y_1$ до $y_2$ заканчивается в точке $x_2$;

и затем как-то пройтись по этим событиям в порядке увеличения $x$ и посчитать общую площадь подобно тому, как мы делали с одномерными отрезками.

Источник

Как найти площадь прямоугольников с учётом пересечений (объединение прямоугольников) за O(n log n)

Задача: На плоскости есть много прямоугольников. Их стороны параллельны осям координат. Нужно посчитать занимаемую ими площадь. Так же нужно учитывать то что они пересекаются. И всё бы хорошо, только прямоугольников целых 100000, а их координаты достигают 10^14 (ага, и размеры ~10^18)! Я придумал только такое решение:
Используем метод сканирующей прямой. Сортируем по x все вертикальные стороны. Проходимся по ним, и соответственно формула при переходе прямой такая:
S_new = DELTA_X * active_ys;
Где DELTA_X — насколько переместилась сканирующая прямая, а active_ys — суммарная высота пересекающих линию прямоугольников.
И проблема как раз таки в вычислении этого active_ys. Можно сохранять все высоты прямоугольников как отрезки, и потом их складывать с учётом пересечений, но у меня это получается только за O(Y) (где Y — кол-во отрезков), и сложность всего алгоритма получается O(NY), а т.к. в худшем случае Y = N, то выходит O(N^2), что разумеется очень плохо. Можно было бы хранить все точки по y, но учитывая ограничения по координатам (10^14) ни в какую память это не влезет. Еще была идея хранить в дереве отрезков все эти отрезки, но непонятно как их суммировать, т.к. они ведь могут и не пересекаться, и задача по сути вернётся к исходной. К тому же эти отрезки надо ещё и удалять. Может кто-то знает как можно решить эту задачку хотя бы за O(n log n)?

возможно глупая идея, потому просто комментом напишу. У вас же проблема в том, что прямоугольники пересаются, иначе можно было бы просто все плошади сложить, так? А что если отсортировать все прямоугольники, идти слева направо, находить все пересекающиеся прямоугольники и делить их на более мелкие прямоугольники, но которые уже не пересекаются? Типа если 2 прямоугольника пересекаются, то убрать их и вместо них добавить прямоугольники (до 5 штук), но которые уже не пересекаются? Интуиция говорит, что это вроде можно за логарифм сделать, и потом за линию сложить все площади.

возможно, но мне кажется что не сработает, т.к. уже разделённые прямоугольники могут опять пересекаться с чем-нибудь, значит и для них тоже надо проводить проверку, и может так выйти что можно эти прямоугольники почти до бесконечности делить.

Заметаете прямой. Статус — дерево отрезков, которое хранит минимум числа покрытий (прямоугольниками) для точки. Такое дерево обновляется за логарифм при добалении/убавлении прямоугольника. Всего будет nlogn.

для точки — если имеете ввиду каждую y-точку на прямой, то этих точек у меня примерно 10^18*2, не думаю что влезет в оперативку.

Все горизонтальные стороны прямоугольников сортируете. Получаете 2 * 10^5 — 1 отрезков на вертикальной прямой. Собираете их в дерево. При заметании вертикальной прямой добавление/удаление прямоугольника влияет на отрезки целиком, не на отдельные точки.

Источник