ZOJ Problem Set - 2508
As Roy has described in his simple problem of SunnyCup 2005, a typical windows platform may have several windows on the desktop. A user's operation may be as simple as a single click of the mouse. In the implementation of such a windows platform, one of the simplest tasks would be deciding which window has been clicked.
Your task is still that given a set of windows, for each mouse click, decide which window has been clicked. Please notice that windows may overlap, and the window on top would receive the click rather than others. This problem is less simple because a window WILL be activated to the top by a click. And more, two consecutive clicks at the same point on the title area of a window are considered as a double-click and will maximize the window, and a double-click on the title area of a maximized window will restore its original shape. A window or its title area is considered being clicked even if the mouse is just on its edge or corner.Input
The input consists of several test cases.
For each case, 4 positive integers are given in the first line: N (<= 5) -- the number of windows, H -- the height of the title area, Wmax and Hmax -- the width and height of a maximized window, respectively. Then N lines follow, each containing four integers, x1, y1, x2, y2, (x1<x2, y2<y1, H<(y1-y2)) the coordinates of the upper-left and lower-right corners of a window. The origin is at the lower-left corner of the screen. The windows are given in back-to-front order.
After the initial positions of windows, a positive integer M (<= 30) is given, indicating the number of mouse clicks. Then M lines follow, each containing two integers, x and y, the coordinates of a mouse click.Output
For each test case, print in a line the indices (starting from 0) of the windows which receive clicks in the input. If there is no such window, output "-1" instead. The indices must be separated by a space and there must be no extra space at the end of a line.Sample Input:
5 20 1280 1024 50 100 100 50 100 100 150 50 100 150 150 100 50 150 100 100 75 125 125 75 9 1 1 55 91 85 80 101 130 101 130 99 101 1280 1004 1280 1004 99 101 1 20 1280 1024 50 150 150 50 2 100 135 1000 1000Sample Output:
-1 0 0 2 2 2 2 2 4 0 -1
Author: CHEN, Yue
Source: CYJJ's Funny Contest #1, Killing in Seconds