Подсчет областей
Подсчет областей
Набор прямоугольников расположен на плоскости 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 (1 ≤ n ≤ 50) - количества прямоугольников на плоскости. Каждая из следующих n строк описывает один прямоугольник. i-ая строка содержит четыре целых числа l_i, t_i, r_i и b_i - координаты i-го прямоугольника; (l_i, t_i) задают x-y координаты верхнего левого угла, а (r_i, b_i) - координаты нижнего правого угла прямоугольника (0 ≤ l_i < r_i ≤ 10^6, 0 ≤ b_i < t_i ≤ 10^6 для 1 ≤ i ≤ n). Четыре целых числа разделены одним пробелом.
Входные данные завершаются одним нулем.
Выходные данные
Для каждого теста вывести в отдельной строке количество областей, на которое плоскость разбивается сторонами прямоугольников.
Рисунок 1. Три прямоугольника разбивают плоскость на шесть областей. Соответствует первому тесту. Оси x- и y-приведены только для иллюстрации, они не делят плоскость.
Рисунок 2. Прямоугольники перекрываются более сложным образом. Соответствуют второму тесту.
Пример
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
8 6 6