ACMP 632: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=632 ACMP #632 — Отрезки] == Похожие задачи == * Интер…») |
(нет различий)
|
Текущая версия от 00:11, 10 января 2016
Ссылка на задачу
Похожие задачи
Комментарии
Отрезков мало, и содержащие их прямые разбивают прямоугольник не более чем на (51 × 51) частей.
Сжимаем координаты и рассматриваем неявный граф-решётку на ~2500 вершинах-прямоугольниках. Для каждого прямоугольника за O(N) проверяем, соединён ли он с левым соседом и верхним соседом; если да, объединяем их (и их площади) в DSU.
Ответом будет множество площадей, соответствующих корням оставшихся в DSU связных компонент.