当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1255:Floors

题目描述
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
输出样例
60000
90000

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-1255

最后修改于 2020-10-29T05:59:06+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 10000