Количество пересечений прямоугольников

Дан набор прямоугольников на плоскости со сторонами, параллельными осям координат.

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

Определение: два прямоугольника пересекаются, если существует область ненулевой площади, принадлежащая обоим прямоугольникам. Внешнее касание по стороне образует общую область нулевой площади, поэтому пересечением не является.


Формат ввода
В первой строке дано целое число n (1 ≤ n ≤ 100 000) — количество прямоугольников.

В следующих n строках заданы описания прямоугольников: целые числа xL, yL, xR, yR (-10^9 ≤ xL, yL, xR, yR ≤ 10^9; xL < xR; yL < yR) — координаты левого нижнего и правого верхнего углов.

Формат вывода
В единственной строке выведите через пробел n чисел: i-е число равно количество прямоугольников, пересекающихся с i-м в порядке ввода прямоугольником.

Пример:
Ввод:
6
-2 -4 2 2
-2 -4 0 -1
-2 -1 0 2
0 -4 2 -1
0 -1 2 2
-1 -2 1 0

Вывод:
5 2 2 2 2 5

Примечания.
Рассмотрим тестовый пример:

Прямоугольник 1 (-2 -4 2 2) включает в себя все остальные прямоугольники из списка, поэтому и пересекается с каждым из них.
Прямоугольник 2 (-2 -4 0 -1) пересекается только с прямоугольниками 1 и 6 (-1 -2 1 0). Обратите внимание, что с прямоугольниками 3 (-2 -1 0 2) и 4 (0 -4 2 -1) пересечений нет, так как данные прямоугольники только касаются прямоугольника 2 по внешней стороне, но не образуют с ним общую область ненулевой площади.
Аналогично прямоугольники 3, 4 и 5 пересекаются только с прямоугольниками 1 и 6.
Прямоугольник 6 находится полностью внутри прямоугольника 1, а так же пересекается частью своей области с каждым из прямоугольников 2, 3, 4, 5.

Я понял что надо искать прямоугольники, которые не пересекаются - пройтись по массиву координат слева направо, справо налево, сверху вниз и снизу вверх, считая прямоугольники которые закрылись (закончились). Но появилась проблема с тем, что некоторые прямоугольники можно так два раза посчитать. Для этого мне порекомендовали использовать дерево отрезков. Я почитал про него и понял, что надо разделить плоскость на меньшие прямоугольники и идти по ним с помощью заметающей прямой. Но я не понял что именно храним в дереве и как получаем ответ для каждого прямоугольника.
Может кто разъяснить как же решить эту задачку за n*log(n)?
Заранее спасибо.

0

DarkShaddow, смотрите сканлайн, он же метод сканирующей прямой

Добавлено через 2 минуты
Если останутся вопросы - завтра разъясню подробно

0

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

0

может и не совсем в тему, но вот пример сравнения готовых объектов-прямоугольников (a&b), исходный код для них возможно тоже где-то здесь

0

Сообщение от DarkShaddow Но я не понял что именно храним в дереве и как получаем ответ для каждого прямоугольника.

Ок, давайте наведем резкость.
Пусть сканирование у нас идет снизу вверх. Прямоугольник задается парой горизонтальных ребер. Назовем нижнее ребро входящим, верхнее ребро - уходящим.
Введем также понятие активных прямоугольников - это прямоугольники, пересекающиеся со сканирующей прямой. Если пересечение идет по стороне, то считаем активным пересечение только по нижней стороне. Входящее ребро активного прямоугольника назовем активным ребром.
Теперь рассмотрим произвольный уровень сканирования.
Сначала обрабатываем уходящие ребра, лежащие на сканпрямой. Деактивируем соответствующий прямоугольник и финализируем его результат.
Теперь входящие ребра. Присваиваем прямоугольнику значение, равное количеству активных ребер, которые пересекает его входящее ребро. И соответственно таким активным ребрам (точнее прямоугольникам) добавляем по единице.
Для реализации необходимо уметь считать количество активных значений, попадающих в некоторый промежуток. А также быстро добавлять по 1 значениям, аргументы которых попадают в заданный подотрезок.
Со всем этим и справляется дерево отрезков.Общая асимптотика О(n log n)

Придумал также другой способ реализации - блочный сортированный список, который в среднем позволяет найти результат фактически за O(n), но это уже другая песня.

Добавлено через 4 минуты

Сообщение от Red white socks Со всем этим и справляется дерево отрезков.Общая асимптотика О(n log n)

Чтобы не было недопонимания - здесь требуется 4 дерева:
1) для подсчета пересечений входящего ребра
2) для увеличения значений на 1
В каждом случае требуется по отдельному дереву для левых и правых концов

0

Честно не совсем понял, но допустим даны следующие 5 прямоугольников:
1) 1, 1 3, 3
2) 0, -2 2, 1
3) 2, -2 4, 2
4) 0, -1 4, 1
5) 1, -5 4, -4

Сообщение от Red white socks Пусть сканирование у нас идет снизу вверх.

Добавим координаты 2х не указанных углов, отсортируем все по X (а если X совпадает, то Y от меньшего к большему), а также пронумеруем прямоугольники и пометим координаты (0 - верхняя координата, 1 - нижняя координата):

0, -2, 1, 2
0, -1, 1, 4
0, 1, 0, 2
0, 1, 0, 4
1, -5, 1, 5
1, -4, 0, 5
1, 1, 1, 1
1, 3, 0, 1
2, -2, 1, 2
2, 1, 0, 2
2, -2, 1, 3
2, 2, 0, 3
3, 1, 1, 1
3, 3, 0, 1
4, -5, 1, 5
4, -4, 0, 5
4, -2, 1, 3
4, -1, 1, 4
4, 1, 0, 4
4, 2, 0, 3

Сообщение от Red white socks ведем также понятие активных прямоугольников. Если пересечение идет по стороне, то считаем активным пересечение только по нижней стороне.

То есть считаем сколько прямоугольников открыто на каждом x, y? Но не понял, что значит пересечение по нижней стороне.
Далее я так понимаю надо разбить всю плоскость на прямоугольники. По итогу получаем 7 горизонталей, поэтому дерево будет длинной 8 (изначально заполнено нулями).

Сообщение от Red white socks Сначала обрабатываем уходящие ребра, лежащие на сканпрямой. Деактивируем соответствующий прямоугольник и финализируем его результат.

Тут вообще не понятно, что значит "Деактивируем" (вычесть где-то 1? там мы вроде и не прибавлали) и какой по итогу результат?

Сообщение от Red white socks Теперь входящие ребра. Присваиваем прямоугольнику значение, равное количеству активных ребер, которые пересекает его входящее ребро. И соответственно таким активным ребрам (точнее прямоугольникам) добавляем по единице.

Окей, каждый раз когда встречаем нижнее (входящее) ребро, то прибавляем 1
Потом идем по массиву и считаем что-то для каждом уровне X:
x=0 x=1 x=2 x=3 x=4
(y=-5) 0
(y=-4) 0
(y=-2) 0
(y=-1) 0
(y=1) 0
(y=2) 0
(y=3) 0
(доп.) 0

Короче сколько бы раз не перечитывал все равно не понял, что делаем, зачем нам активные ребра искать, как ответ получать и тд и тп

Миниатюры

   

0

DarkShaddow, возможно (судя по вашим фразам), что вам стоит пока набить руку со скайлайном и дереву отрезков на задачах попроще.

0

DarkShaddow, получилось решить или нет?

0

DmitriyKova, не-а, а что такая же задачка где-то попалась?

0

DarkShaddow, да, в контесте компании одной известной

0