This page is still under construction.

Parts of this page are still being built. What you see may change.

Tin Cutter

Time limit1sMemory limit128 MB

Summary
Given up to 100 axis-parallel cuts inside a plate, count how many holes (closed regions not touching the plate border) remain after all cuts are made.
Level

Hard8 of 10

Topics
Geometry, Graph, DFS, Implementation
Solved
No attempts yet

Problem

In a tin-cutting factory there is a machine that cuts parts out of tin plates. Its extremely sharp knife can make horizontal or vertical straight cuts in a plate. One cutting process is a sequence of such cuts. Every cut is described by its two endpoints, which always lie inside the plate. As the cuts are made, pieces of the plate may fall out, so holes can appear in the plate.

The factory needs to know how many holes remain in the plate after a given sequence of cuts. Write a program that computes this number. A single, isolated cut is never counted as a hole.

Below are some situations that can occur after cutting:

two holestwo holesone holeone hole

Input

The input consists of several blocks of lines. Every block except the last one describes one cutting process. The first line of a block contains an integer NN (N≤100N \le 100), the number of cuts in that process. Each of the next NN lines describes one cut in the form X1 Y1 X2 Y2X_1\ Y_1\ X_2\ Y_2, where (X1,Y1)(X_1, Y_1) and (X2,Y2)(X_2, Y_2) are the coordinates of the endpoints of the cut, separated by single spaces. All coordinates are integers, and every cut is horizontal or vertical (that is, parallel to the xx or yy axis).

The last block consists of a single line containing 00 and does not describe a cutting process.

Output

For every block of the input except the terminating block, print one line containing the number of holes that remain in the plate after all cuts of that block have been made.

Nothing is printed for the final terminating block.

Examples1

  1. Example 1

    Input
    4
    0 1 1 1
    1 1 1 0
    1 0 0 0
    0 0 0 1
    2
    0 1 2 1
    1 2 1 0
    0
    
    Expected output
    1
    0