|Online Judge||Problem Set||Authors||Online Contests||User|
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.
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.
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.
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
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator