Floors
Time Limit: 1 Second Memory Limit: 32768 KB
The new highway promised a better and faster connection between A and B and
a considerable reduction of congestion. Unfortunately there was an obstacle:
the old mansion. This conflict was soon resolved in favor of the highway.
Shortly before the demolition of the mansion was about to start, a lover of
old mansions found out that the colorfully tiled floors in the mansion were
designed by the famous painter Mondriaan, and therefore had great cultural value.
They should be saved. They should be removed from the mansion before the mansion
will be demolished.
A floor moving expert was hired to accomplish the job. He decided to cut each
floor into smaller pieces, in order to make it more tractable. He possessed
a fine floor cutting tool which enabled him to cut a rectangular piece of floor
into two smaller rectangular pieces, cutting parallel to one of the sides. Of
course the cutting should be between tiles; cutting through a tile was not an
option. This way the floor in Figure 1 could easily be cut into 9 tiles. The
floor in Figure 2
however can not be cut into smaller pieces. The floor in Figure 3 can be cut
into six pieces, but one of the parts will consist of several tiles.
While preparing for the job, the floor moving expert was anxious to know how large the remaining pieces could be: would they be heavy, very heavy or extremely heavy? What kind of floor lifting tool should be hired? Because the floors have a fixed thickness, and a fixed density, the weight of a piece of floor only depends upon its area.
Given a rectangular floor covered with rectangular tiles, find the area of the largest piece, after the floor is cut into the smallest possible pieces. The words smallest and largest refer to the area of the pieces. Cutting through a tile is not allowed. A cut through a rectangle is always parallel to one of the sides, and through the full length (or width) of the rectangle.
Input
The input contains several floors. The first line of the input gives the number
of floors.
Each floor is described in several lines. The first line contains two positive
integers: the length and width of the floor, in millimeters. A floor is at most
40 000 mm long or wide. The next line contains a single number: the number t
of tiles (1 <= t <= 100). The following t lines each contain the description
of a tile. A tile is given as four integers:
xl yl xh yh
where (xl, yl) are the coordinates of the lower left corner of the tile, and
(xh, yh) are the coordinates of the upper rightmost corner of the tile. A tile
always has a positive area. The order of the coordinates of the floor and those
of the tile coincide, of course.
You may assume that the tiles are mutually disjoint, and cover the floor, the
whole floor, and nothing but the floor.
Output
For each test case (each floor) the output contains a number, on a single line: the area of the largest piece of floor (in square millimeters), after cutting the floor into the smallest pieces possible, with the given restrictions.
Sample Input
2 300 400 3 0 0 300 200 0 200 200 400 200 200 300 400 300 300 5 0 0 200 100 200 0 300 200 0 100 100 300 100 200 300 300 100 100 200 200
Sample Output
60000 90000Submit
Source: Northwestern Europe 2002