eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Подсчет областей

Подсчет областей

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Набор прямоугольников расположен на плоскости x-y. Все четыре стороны прямоугольников параллельны либо оси x, либо оси y, все прямоугольники расположены в границах, заданных ниже. Никаких других ограничений на координаты прямоугольников нет.

Плоскость разделена на области, границами которых являются стороны одного или нескольких прямоугольников. В примере, приведенном на Рисунке 1, три прямоугольника перекрывают друг друга, в результате чего плоскость разделена на восемь областей.

Прямоугольники могут перекрываться и более сложным способом. Например, два прямоугольника могут перекрываться по сторонам, могут иметь общие угловые точки, и/или быть вложенными. Рисунок 2 отображает эти случаи.

Напишите программу, которая вычислит количество областей на плоскости, разделенной прямоугольниками.

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

Состоит из нескольких тестов. Каждый тест имеет следующий формат:

n

l_1 t_1 r_1 b_1

l_2 t_2 r_2 b_2

...

l_n t_n r_n b_n

Каждый тест начинается со значения n (1n50) - количества прямоугольников на плоскости. Каждая из следующих n строк описывает один прямоугольник. i-ая строка содержит четыре целых числа l_i, t_i, r_i и b_i - координаты i-го прямоугольника; (l_i, t_i) задают x-y координаты верхнего левого угла, а (r_i, b_i) - координаты нижнего правого угла прямоугольника (0l_i < r_i10^6, 0b_i < t_i10^6 для 1in). Четыре целых числа разделены одним пробелом.

Входные данные завершаются одним нулем.

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

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

Рисунок 1. Три прямоугольника разбивают плоскость на шесть областей. Соответствует первому тесту. Оси x- и y-приведены только для иллюстрации, они не делят плоскость.

Рисунок 2. Прямоугольники перекрываются более сложным образом. Соответствуют второму тесту.

Пример

Входные данные #1
3
4 28 27 11
15 20 42 5
11 24 33 14
5
4 28 27 11
12 11 34 2
7 26 14 16
14 16 19 12
17 28 27 21
2
300000 1000000 600000 0
0 600000 1000000 300000
0
Выходные данные #1
8
6
6
Источник ACM International Collegiate Programming Contest, Asia Regional Contest, Aizu, 2013–11–24