https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=ACMP_632 2026-05-13T12:10:37Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=ACMP_632&diff=1956&oldid=prev 2016-01-10T00:11:23Z

<p>Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&amp;id_task=632 ACMP #632 — Отрезки] == Похожие задачи == * Интер…»</p> <p><b>Новая страница</b></p><div>== Ссылка на задачу ==<br /> * [http://acmp.ru/?main=task&amp;id_task=632 ACMP #632 &amp;mdash; Отрезки]<br /> <br /> == Похожие задачи ==<br /> * [[Интернет-олимпиада 25.03.2006, усложнённый уровень, H]]<br /> <br /> == Комментарии ==<br /> Отрезков мало, и содержащие их прямые разбивают прямоугольник не более чем на (51 &amp;times; 51) частей.<br /> <br /> Сжимаем координаты и рассматриваем неявный граф-решётку на ~2500 вершинах-прямоугольниках. Для каждого прямоугольника за O(N) проверяем, соединён ли он с левым соседом и верхним соседом; если да, объединяем их (и их площади) в DSU.<br /> <br /> Ответом будет множество площадей, соответствующих корням оставшихся в DSU связных компонент.<br /> <br /> <br /> [[Category: Сборник задач: ACMP]]<br /> [[Category: Задачи: Сжатие координат]]<br /> [[Category: Задачи: Система непересекающихся множеств]]</div>

Ctrlalt