Rectangle Cutting
Time limit1sMemory limit128 MB
Given a small cake and several rectangular outlines cut into it, count the number of connected pieces the cake is divided into.
- Level
Medium6 of 10
- Topics
- BFS, Implementation, Geometry, Simulation
- Solved
- No attempts yet
Problem
In a small historic village, a popular wedding-ceremony activity is called rectangle cutting. Each close relative of the bride comes up and cuts a rectangle into the wedding cake (but does not take a piece). The cake has a rectangular shape, and the task is to count how many pieces the cake is divided into after all the cuts.
For example, in the figure below the cake is 3×5 (height × width) and three people have each made a rectangular cut. As a result, the cake is split into six pieces.

Each rectangular cut is described by the coordinates of two opposite corners. Only the outline (the four edges) of each rectangle is cut; no cake is removed. The cuts in the figure correspond to the first sample test case. Because families here can be large, the number of pieces can also be large, so a program is needed to compute it.
Input
The input contains several test cases. Each test case spans several lines. The first line contains two integers and () — the height and the width of the cake. The second line contains a single integer () — the number of people who cut a rectangle. Each of the following lines contains four integers , , , , the coordinates of two opposite corners of one cut, where and (the -axis runs along the width, the -axis along the height). The input ends with a line containing two zeros, which is not processed.
Output
For each test case, output a single line containing the number of pieces the cake is cut into.