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

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

1 секунда

256 мегабайтів

Дуже легка

На площині $x$ - $y$ розташовано кілька прямокутників. Усі сторони цих прямокутників паралельні або осі $x$ , або осі $y$ , і всі вони знаходяться в межах, зазначених нижче. Інших обмежень на координати прямокутників немає.

Площина поділена на області, межами яких є сторони одного або кількох прямокутників. Наприклад, на Рисунку 1 три прямокутники перекриваються, утворюючи шість областей.

Прямокутники можуть перекриватися складніше. Наприклад, два прямокутники можуть мати спільні сторони, спільні кутові точки або бути вкладеними один в одного. Рисунок 2 демонструє ці випадки.

Напишіть програму, яка підрахує кількість областей на площині, розділеній прямокутниками.

Вхідні дані

Вхідні дані складаються з кількох тестів. Кожен тест має такий формат:

$n$

$l_{1} t_{1} r_{1} b_{1}$ l_1\ t_1\ r_1\ b_1

$l_{2} t_{2} r_{2} b_{2}$ l_2\ t_2\ r_2\ b_2

$\dots$

$l_{n} t_{n} r_{n} b_{n}$ l_n\ t_n\ r_n\ b_n

Кожен тест починається зі значення $n$ ( $1 \leq n \leq 50$ 1 \leq n \leq 50) — кількості прямокутників на площині. Кожен із наступних $n$ рядків описує один прямокутник. $i$ -ий рядок містить чотири цілі числа $l_{i}$ l_i, $t_{i}$ t_i, $r_{i}$ r_i і $b_{i}$ b_i — координати $i$ -го прямокутника; ( $l_{i}$ l_i, $t_{i}$ t_i) задають $x$ - $y$ координати верхнього лівого кута, а ( $r_{i}$ r_i, $b_{i}$ b_i) — координати нижнього правого кута прямокутника ( $0 \leq l_{i} < r_{i} \leq 1 0^{6}$ 0 \leq l_i < r_i \leq 10^6, $0 \leq b_{i} < t_{i} \leq 1 0^{6}$ 0 \leq b_i < t_i \leq 10^6 для $1 \leq i \leq n$ 1 \leq i \leq n). Чотири цілі числа розділені одним пробілом.

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

Вихідні дані

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

Рисунок 1. Три прямокутники розбивають площину на шість областей. Відповідає першому тесту. Осі $x$ і $y$ наведені лише для ілюстрації, вони не ділять площину.

Рисунок 2. Прямокутники перекриваються більш складним чином. Відповідають другому тесту.

Приклади

Приклад 1