Pro.ID22769 TitleDecorate the wall Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22769 AC4 Submit7 Ratio57.14% 时间&空间限制描述After building his huge villa, Mr. Rich cannot help but notice that the interior walls look rather blank. To change that, he starts to hang paintings from his wonderful collection. But soon he realizes that it becomes quite difficult to find a place on the wall where a painting can be placed without overlapping other paintings. Now he needs a program which would tell him, given the already placed paintings, where to place the next painting without moving any other paintings (or indicating that this is impossible). Paintings have a rectangular shape and are to be placed parallel to the side of the wall. If you do not mind a nice reward from Mr. Rich, go on and solve the problem. 输入The first line of the input file contains a number representing the number of test cases to follow. Each test case starts with a line containing three numbers n, w and h. n is the number of paintings already hanging on the wall, w is the width of the wall and h is the height of the wall. The next n lines contain 4 integers x1, y1, x2, y2 each (0 ≤ x1 < x2 ≤ w, 0 ≤ y1 < y2 ≤ h); the x-coordinates give the distance to the left end of the wall, the y-coordinates give the distance to the bottom of the wall. (x1, y1) is the position of the lower left corner of a painting, (x2, y2) is the position of the upper right corner. The last line of each test case contains the dimensions of the next painting to be placed, first its width w', then its height h' (1 ≤ w' ≤ w, 1 ≤ h' ≤ h). You are not allowed to rotate the painting. You can assume that 0 ≤ n ≤ 200 and 1 ≤ w, h ≤ 1000000. Moreover, all paintings already hanging do not overlap. 输出Description After building his huge villa, Mr. Rich cannot help but notice that the interior walls look rather blank. To change that, he starts to hang paintings from his wonderful collection. But soon he realizes that it becomes quite difficult to find a place on the wall where a painting can be placed without overlapping other paintings. Now he needs a program which would tell him, given the already placed paintings, where to place the next painting without moving any other paintings (or indicating that this is impossible). Paintings have a rectangular shape and are to be placed parallel to the side of the wall. If you do not mind a nice reward from Mr. Rich, go on and solve the problem. Input The first line of the input file contains a number representing the number of test cases to follow. Each test case starts with a line containing three numbers n, w and h. n is the number of paintings already hanging on the wall, w is the width of the wall and h is the height of the wall. The next n lines contain 4 integers x1, y1, x2, y2 each (0 ≤ x1 < x2 ≤ w, 0 ≤ y1 < y2 ≤ h); the x-coordinates give the distance to the left end of the wall, the y-coordinates give the distance to the bottom of the wall. (x1, y1) is the position of the lower left corner of a painting, (x2, y2) is the position of the upper right corner. The last line of each test case contains the dimensions of the next painting to be placed, first its width w', then its height h' (1 ≤ w' ≤ w, 1 ≤ h' ≤ h). You are not allowed to rotate the painting. You can assume that 0 ≤ n ≤ 200 and 1 ≤ w, h ≤ 1000000. Moreover, all paintings already hanging do not overlap. Output Produce one line of output for each test case. Write "Fail!" if there is no place left on the wall where the painting could be placed without overlapping other paintings. Otherwise, write the coordinates where the lower left corner of the painting should be placed. In case there is more than one solution, select the solution with a minimum y-coordinate, and break ties using the minimum x-coordinate. Sample Input 2 Sample Output Fail! Hint The following image illustrates the second sample test case:
Source 样例输入2 样例输出Fail! 提示The following image illustrates the second sample test case:
|
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-5 22:02 , Processed in 0.035454 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
