Hole Cutter
Time limit1sMemory limit128 MB
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.
Input
The input consists of several cutting-operation descriptions. Each description starts with a line containing an integer , the number of cuts in the operation, where . This line is followed by lines giving the actual cuts. Each cut is given by four integers separated by single spaces, , with . is the start point of the cut line and 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 -axis or the -axis. The input is terminated by a cutting-operation description with , i.e. a line consisting of a single .
Output
For each cutting operation, output a single line containing the sentence There are H holes., where 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.



