ACMP 632
(перенаправлено с «Интернет-олимпиада 25.03.2006, усложнённый уровень, H»)
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Похожие задачи
Комментарии
Отрезков мало, и содержащие их прямые разбивают прямоугольник не более чем на (51 × 51) частей.
Сжимаем координаты и рассматриваем неявный граф-решётку на ~2500 вершинах-прямоугольниках. Для каждого прямоугольника за O(N) проверяем, соединён ли он с левым соседом и верхним соседом; если да, объединяем их (и их площади) в DSU.
Ответом будет множество площадей, соответствующих корням оставшихся в DSU связных компонент.