ScanLine ~ Сириус 04.06
КОНСПЕКТ ЕЩЕ ПИШЕТСЯ!!!
Задача - Объединение прямоугольников
Задача заключается в том, что на плоскости имеется N прямоугольников,
стороны которых параллельны осям координат. Требуется вычислить площадь объединения данных прямоугольников
Тупняк - Сделаем буловую табличку, по размеру достаточную, чтобы туда поместились все наши прямоугольники. Перебираем все прямоугольники. Смотрим на очередной. Поставим в табличку единички в те клетки, которые лежат в каждом прямоугольнике. Это работает за 𝒪(𝑛𝑆), где 𝑆 — площадь таблички, так как мы 𝑛 раз проходим по табличке площади 𝑆.
Решение за 𝒪(𝑛 log 𝑛) - Здесь мы сжимаем координаты.
Теперь будем хранить одну вертикальную полоску длины, равной высоте таблицы. Хранить будем, как массив интов. Делаем сканалйн по 𝑥-ам. В этой полоске поддерживаем сколько из еще открытых прямоугольников имеют данную координату по 𝑥. Открылся новый прямоугольник — ко всем нужным 𝑦 в полоске прибавили единичку. Закрылся — вычитаем единичку. Чтобы найти площадь на текущем столбце, нужно сложить площади всех точек, в которых
записан не ноль. Получили сложность 𝒪(𝑛2). Можно оптимизировать с помощью ДО на 𝒪(𝑛 log 𝑛)
Так же ссылочка на решение челика на Codeforces - https://codeforces.com/blog/entry/49797
Задача - Найти точку, накрытой наибольшим количеством прямоугольников
Даны n прямоугольников. Надо найти точку, которая покрыта максимальным количеством прямоугольников.
Решение человека с Codeforces:
Давайте возьмем y-координаты всех точек, для которых нужно определить количество прямоугольников, покрывающих их, и отметим их на вертикальной прямой, находящейся в x = - ∞. Давайте теперь начнем непрерывно двигать эту прямую до x = + ∞ и поддерживать для каждой точки количество прямоугольников, покрывающих ее.
Собственно, вопрос: а в какие моменты данные количества будут изменяться? Ответ: когда наша прямая "входит" в прямоугольник (то есть, проходит через координату x = xleft и когда она "выходит" из него (проходит через координату x = xright). Ну, собственно говоря, мы можем построить отсортированный массив т.н. "событий", где события — это вход в прямоугольник, выход из прямоугольника и ответ на запрос количества покрывающих точку прямоугольников. Соответственно, для события входа в прямоугольник мы прибавляем единичку на отрезке [ybottom; ytop], для события выхода из прямоугольника — отнимаем единичку на соответствующем отрезке, а для события ответа на запрос — сохраняем значение количества покрывающих точку прямоугольников.
PS - https://codeforces.com/blog/entry/49588
Так же решение человека с форума emaxx (в конце написан код, но как говорит автор, он с багами, но баги в ДО) - https://e-maxx.ru/forum/viewtopic.php?id=368
Задача - Сумма на прямоугольнике
Решение - в конце конспект Сергея Слотина
Крутой конспект - https://archive.lksh.ru/2018/august/B'/notes/03.pdf
Так же интересный конспект от Сергея Слотина - https://ru.algorithmica.org/cs/decomposition/scanline/