This page is still under construction.

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

Hole Cutter

Time limit1sMemory limit128 MB

Summary
Given axis-parallel cuts strictly inside a sheet, count how many distinct holes the cuts create.
Level

Medium7 of 10

Topics
Geometry, Union-find, Combinatorics
Solved
No attempts yet

Problem

The assistants at the main office often need to cut various shapes out of a large sheet of paper — for example, to hand out posters of many different sizes. They have just acquired a new cutter that can make cuts far more freely than any of their previous machines, and they want a program that computes exactly what happens when a complex series of cuts is made. In particular, they need to know how many holes are formed in the sheet by the cuts. The pictures below show some situations that can arise after cutting.

Two holesTwo holesOne holeOne hole

Input

The input consists of several cutting-operation descriptions. Each description starts with a line containing an integer NN, the number of cuts in the operation, where 1≤N≤1001 \le N \le 100. This line is followed by NN lines giving the actual cuts. Each cut is given by four integers separated by single spaces, X1,Y1,X2,Y2X_1, Y_1, X_2, Y_2, with −105<X1,Y1,X2,Y2<105-10^5 < X_1, Y_1, X_2, Y_2 < 10^5. (X1,Y1)(X_1, Y_1) is the start point of the cut line and (X2,Y2)(X_2, Y_2) is its end point.

You may assume the points are always strictly inside the sheet, never on its boundary. Each cut is parallel to the xx-axis or the yy-axis. The input is terminated by a cutting-operation description with N=0N = 0, i.e. a line consisting of a single 00.

Output

For each cutting operation, output a single line containing the sentence There are H holes., where HH is the number of distinct holes in the sheet after all the cuts have been made. Note that the minimum area of any hole is 1 square unit.

Examples4

  1. Example 1

    Input
    6
    1 0 1 1
    2 0 2 2
    3 1 3 2
    1 0 2 0
    1 1 3 1
    2 2 3 2
    2
    0 1 2 1
    1 2 1 0
    0
    
    Expected output
    There are 2 holes.
    There are 0 holes.
    
  2. Example 2

    Input
    4
    0 0 1 0
    1 0 1 1
    1 1 0 1
    0 1 0 0
    0
    
    Expected output
    There are 1 holes.
    
  3. Example 3

    Input
    1
    0 0 0 5
    0
    
    Expected output
    There are 0 holes.
    
  4. Example 4

    Input
    8
    0 0 4 0
    4 0 4 4
    4 4 0 4
    0 4 0 0
    1 1 3 1
    3 1 3 3
    3 3 1 3
    1 3 1 1
    0
    
    Expected output
    There are 2 holes.