Tin Cutter
Time limit1sMemory limit128 MB
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:
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 (), the number of cuts in that process. Each of the next lines describes one cut in the form , where and 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 or axis).
The last block consists of a single line containing 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.



