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

Chinese Ink

Chinese Ink

Lucca, my four-years-old daughter, loves drawing polygons in bond paper. For example, yesterday she drew two squares, a rectangle and two triangles: \includegraphics{https://static.e-olymp.com/content/17/17cbdc9a41665da6e51b7b0acfff81fdaea25b6b.jpg} Today, she wanted to fill her figures with black chinese ink. I helped her, obtaining the next result: \includegraphics{https://static.e-olymp.com/content/28/28ad7a68f6ee2ec673798a19ce4366f9b22145de.jpg} She asked me: how many black zones do you see?. I said: two. I'm bored answering the same question everyday. Can you help us writing a program that, given a collection of black filled polygons, determines the number of black zones on the drawing? For a precise understanding: a \textit{black zone} is a region of black coloured points on the sheet, where every pair of them may be connected by a continuous line within the region. \InputFile The input consists of several test cases. Each test case is represented as follows: \begin{itemize} \item A line with an integer \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{40}) which indicates the number of polygons in the drawing. \item \textbf{N} lines, one per polygon, each one containing a list of \textbf{2·t} integer numbers \textbf{x_1} \textbf{y_1 x_2 y_2 ... x_t y_t} specifying the points in the boundary of the polygon (\textbf{-10^4} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{10^4}, \textbf{3} ≤ \textbf{t} ≤ \textbf{10}). The drawn polygon is bounded by the closed path composed of the straight line segments \includegraphics{http://uva.onlinejudge.org/external/116/11665img4.png} , \includegraphics{http://uva.onlinejudge.org/external/116/11665img5.png} , ..., \includegraphics{http://uva.onlinejudge.org/external/116/11665img6.png} , and \includegraphics{http://uva.onlinejudge.org/external/116/11665img7.png} . You can suppose that the drawn polygon is a simple polygon (a polygon whose boundary is a non-self-intersecting closed path). \end{itemize} The end of the input is indicated when \textbf{N} = \textbf{0}. \OutputFile For each case in the input, print one line with the number of black zones in the drawing after filling each one of the polygons with black chinese ink.
Лимит времени 2 секунды
Лимит использования памяти 64 MiB
Входные данные #1
5
35 29 179 111 19 145
183 22 305 22 305 80 183 80
232 49 361 49 361 178 232 178
137 94 188 156 112 164
79 144 129 143 129 193 79 193
2
20 20 30 20 30 30 20 30
40 40 40 50 50 50 50 40
2
20 20 30 20 30 30 20 30
30 30 40 30 40 40 30 40
3
20 20 40 20 40 40 20 40
50 30 60 20 70 50
60 40 50 30 30 50
0
Выходные данные #1
2
2
1
1