ZOJ Problem Set - 3005
The biologist Mr.R likes cultivating bacteria on the culture medium. What is interesting is that the new cultivated bacterial colonies always form a rectangle, whose sides are parallel with the x-axis or the y-axis of the plane.
One day, Mr.R cultivated a lot of bacteria on the culture medium. Some of the colonies were overlapping. To his surprise, he found all the new cultivated bacteria defeat the old ones, which means when the new bacteria had been cultivated, the old bacteria lived in the new bacteria's colony disappeared.
Mr.R has picked out some of the bacteria and he wants to know which bacteria have defeated them.
The problem has multiple test cases.
For each test case, the first line contains a integer n (1 <= n <= 500), which represents the total number of bacteria.
The next n lines describe the colonies of the bacteria. Each line has four integers x1 y1 x2 y2 (x1 < x2, y1 < y2, -100,000 <= x1, x2, y1, y2 <= 100,000). They are the coordinates of the left-top and the right-bottom points of the rectangle. The bacteria are numbered from 1 to n. The first rectangle is the colony of the first cultivated bacteria; the second rectangle is the colony of the second cultivated one, etc.
The following line contains a number m ( m <= n ), which means the number of the bacteria that Mr.R picked out.
The last line of the test case contains m numbers (between 1 and n) indicating the picked out bacteria.
For each test case, there are m lines. The first number of each line is the number of the bacteria that have defeated the selected one, and then list them out in increasing order. The first line contains the answer to the first selected bacteria; the second line contains the answer to the second, etc.
Output a blank line after each test case.
3 1 1 5 6 2 2 5 5 3 3 4 4 3 3 2 1 3 1 1 5 5 2 2 4 4 3 3 5 5 3 1 2 3 3 3 3 5 5 2 2 5 5 3 3 5 5 3 1 2 3
0 1 3 1 2 2 2 3 1 3 0 1 2 1 3 0
Author: ZHANG, Zhetao
Source: ZOJ Monthly, July 2008