Sirius 2022
June 4, 2022

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/