e-olymp
Yarışlar

Пятёрка за неделю 22

Графическая маска

В одном из режимов программного пакета Grafix пользователь выделяет часть полотна, используя непрозрачные прямоугольники. Графическое изображение, которое используется в качестве полотна, имеет 400 точек в высоту и 600 точек в ширину. Как только прямоугольники окажутся выделенными, пользователь может выполнить графические операции в невыделенных областях полотна, известных как дырки. Дыркой называется максимальный набор соседних пикселей, не принадлежащих ни одному из непрозрачных прямоугольников. Два пикселя являются соседними, если они прилегают друг к другу по горизонтали или вертикали. Отношение соседства является транзитивным.

На полотне выделено несколько прямоугольников. Найти размеры всех дырок (в точках) и вывести их в возрастающем порядке.

prb2382

Левый рисунок содержит две дырки, а правый девять

Входные данные

Состоит из нескольких тестов. Первая строка каждого теста содержит количество прямоугольников n (1 n50). Каждая из следующих n строк описывает координаты противоположных углов прямоугольника в формате "строка столбец строка столбец" (0строка399, 0столбец599). Первая пара чисел задает координаты верхнего левого угла, а вторая пара - координаты нижнего правого.

Выходные данные

Для каждого теста вывести в отдельной строке размеры всех дырок в возрастающем порядке. Если для некоторого теста дырки на полотне будут отсутствовать, то вывести пустую строку.

Zaman məhdudiyyəti 1.5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
1
0 292 399 307
4
48 192 351 207
48 392 351 407
120 52 135 547
260 52 275 547
Çıxış verilənləri #1
116800 116800
22816 192608