Red Color Or Not

　　Qidiot is learning Computer Graphics now. Simply put, the research of the computer graphics is to study how to display the graphics in the computer, as well as the principles and algorithms of computer graphics computing, processing and displaying. However, due to the display device can not really show the continuous graphics, the graphics would be represented by the small squares (pixels).
　　
　　For example, the figure is a rectangle, whose lower-left corner is (1,1) and upper right corner is (2,2), displayed on the display device.
　　One day, when Qidiot reviews the homework of computer graphics, he paints N rectangles in the blank plane, and fills each rectangle (including its boundaries) into red. In order to see his "painting", he then establishes the window, which is a rectangle area in the plane, to see all of the geometrical image in this rectangle area. Quickly, he establishes K windows. Some windows are "colorful", but nothing changes in many windows. Therefore, Qidiot becomes curious about whether each of windows is filled into red. However, it's so difficult for Qidiot to check these excessive windows, So he wants you to help him check out whether each window is filled into red.

　　There are several test cases.
　　The first line of each test case is an integer N (0<N<=50000), indicating the number of rectangles.
　　The next N lines, each line has 4 integers x1, y1, x2, y2 (-10000000<x1<x2<10000000, -10000000<y1<y2<10000000), which (x1, y1) indicates the lower-left coordinate and (x2, y2) indicates the upper-right of each rectangle.
　　Then there is an integer K (0<K<=5000), indicating the number of windows.
　　The next K lines, each line has 4 integers x1, y1, x2, y2 (-10000000<x1<x2<10000000, -10000000<y1<y2<10000000), which (x1, y1) indicates the lower-left coordinate and (x2, y2) indicates the upper-right of each window.
　　An empty line will separate two test cases. Input is ended with a "0".

　　Each test case outputs K lines, corresponding to each of the windows.
　　If i-th window is filled into red, output "Case #i: Yes". Otherwise output "Case #i: No".
　　Print out a blank line after each test case.

3
-5 -5 0 0
-5 0 0 5
0 -5 5 5
2
-5 -5 5 5
-6 -6 6 6

3
0 0 2 2
1 1 3 3
2 2 4 4
3
0 0 4 4
1 1 4 4
1 1 2 2

0

Case #1: Yes
Case #2: No

Case #1: No
Case #2: No
Case #3: Yes

华南师范大学·2012年ACM程序设计竞赛·决赛

Close | Top

Administration