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

Підрахунок областей

Підрахунок областей

Набор прямоугольников расположен на плоскости \textbf{x-y}. Все четыре стороны прямоугольников параллельны либо оси \textbf{x}, либо оси \textbf{y}, все прямоугольники расположены в границах, заданных ниже. Никаких других ограничений на координаты прямоугольников нет. Плоскость разделена на области, границами которых являются стороны одного или нескольких прямоугольников. В примере, приведенном на \textit{\textbf{Рисунке 1}}, три прямоугольника перекрывают друг друга, в результате чего плоскость разделена на восемь областей. Прямоугольники могут перекрываться и более сложным способом. Например, два прямоугольника могут перекрываться по сторонам, могут иметь общие угловые точки, и/или быть вложенными. \textit{\textbf{Рисунок 2}} отображает эти случаи. Напишите программу, которая вычислит количество областей на плоскости, разделенной прямоугольниками. \InputFile Состоит из нескольких тестов. Каждый тест имеет следующий формат: \textbf{n} \textbf{l_1 t_1 r_1 b_1} \textbf{l_2 t_2 r_2 b_2} \textbf{...} \textbf{l_n t_n r_n b_n} Каждый тест начинается со значения \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50}) - количества прямоугольников на плоскости. Каждая из следующих \textbf{n} строк описывает один прямоугольник. \textbf{i}-ая строка содержит четыре целых числа \textbf{l_i}, \textbf{t_i}, \textbf{r_i} и \textbf{b_i} - координаты \textbf{i}-го прямоугольника; (\textbf{l_i}, \textbf{t_i}) задают \textbf{x-y} координаты верхнего левого угла, а (\textbf{r_i}, \textbf{b_i}) - координаты нижнего правого угла прямоугольника (\textbf{0} ≤ \textbf{l_i} < \textbf{r_i} ≤ \textbf{10^6}, \textbf{0} ≤ \textbf{b_i} < \textbf{t_i} ≤ \textbf{10^6} для \textbf{1} ≤ \textbf{i} ≤ \textbf{n}). Четыре целых числа разделены одним пробелом. Входные данные завершаются одним нулем. \OutputFile Для каждого теста вывести в отдельной строке количество областей, на которое плоскость разбивается сторонами прямоугольников. \includegraphics{https://static.e-olymp.com/content/2d/2d34e6b3eb8b3f0a34bf25a781162ef6b4b8122c.jpg} \textit{\textbf{Рисунок 1}}. Три прямоугольника разбивают плоскость на шесть областей. Соответствует первому тесту. Оси \textbf{x}- и \textbf{y}-приведены только для иллюстрации, они не делят плоскость. \includegraphics{https://static.e-olymp.com/content/0d/0d2f3aa193d85a48b69addd955acccb5f83c1715.jpg} \textit{\textbf{Рисунок 2}}. Прямоугольники перекрываются более сложным образом. Соответствуют второму тесту.
Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB
Вхідні дані #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