2014
03-09

# Windows

Consider the following scenario. The screen has width 200 and height 100. There are three windows on the screen.

The left picture shows the initial configuration. Windows are drawn from bottom to top, according to the ID, so window 1 is at the bottom, and window 3 is at the top. The right picture shows the screen after clicking at (60, 20). Point (60, 20) is in the visible part of window 1, so it is brought to the top (each time a window is clicked, it gets focus, and brought to the top. The relative order of other windows won’t change). If you then click at (150, 90), nothing will change, since it is not within the visible part of any window. Then, after clicking at (150, 30), window 2 will get focus. Note that, each window includes all points on its borders: if its top-left corner and bottom-right corner are (x1,y1) and (x2,y2) respectively, it includes exactly the points (x, y) such that x1 <= x <= x2, y2 <= y <= y1.
Your task is to determine, for each click, the ID of window which is just clicked on (or 0 if no window is clicked).

There will be only one case, beginning with two integer numbers C and R (1 <= C, R <= 10000), the number of columns and rows, respectively. The third line contains an integer n (1 <= n <= 50000), the number of windows. On each of the next n lines, there are four integers x1, y1, x2, y2, the top-left and bottom-right coordinates of the window. The window is non-empty (i.e. x1 < x2, y2 < y1).The window IDs are 1, 2, 3, …, n, in the order they appear in the input. On the next line, there is an integer m (1 <= m <= 100000), the number of mouse clicks. On each of the next m lines, there will be two integers x and y, the coordinate clicked. In the judge input, all the coordinates (x, y) will be randomly generated within the screen (i.e. 1 <= x <= C, 1 <= y <= R).

There will be only one case, beginning with two integer numbers C and R (1 <= C, R <= 10000), the number of columns and rows, respectively. The third line contains an integer n (1 <= n <= 50000), the number of windows. On each of the next n lines, there are four integers x1, y1, x2, y2, the top-left and bottom-right coordinates of the window. The window is non-empty (i.e. x1 < x2, y2 < y1).The window IDs are 1, 2, 3, …, n, in the order they appear in the input. On the next line, there is an integer m (1 <= m <= 100000), the number of mouse clicks. On each of the next m lines, there will be two integers x and y, the coordinate clicked. In the judge input, all the coordinates (x, y) will be randomly generated within the screen (i.e. 1 <= x <= C, 1 <= y <= R).

200 100
3
50 50 80 20
70 60 180 10
10 90 100 40
3
60 20
150 90
150 30

1
0
2

#include<iostream>
#include<string.h>
using namespace std;
const int maxn =101;
int n;
struct rect{
int x1,y1,x2,y2;
};
rect rec[maxn];
int myFind(int a,int b){
for(int i=n-1;i>=0;i--)
if(rec[i].x1<=a && rec[i].x2>=a &&rec[i].y1<=b && rec[i].y2>=b)
return i;
return -1;
}

int main(){
//freopen("in.txt","r",stdin);
for(int m,cases=1;cin>>n &&n;cases++){
for(int i=0;i<n;i++){
int t1,t2;
cin>>rec[i].x1>>rec[i].y1>>t1>>t2;
rec[i].x2=rec[i].x1+t2-1;
rec[i].y2=rec[i].y1+t1-1;
}
cout<<"Desktop "<<cases<<":\n";
cin>>m;
int a,b;
while(m--){
cin>>a>>b;
int ans=myFind(a,b);
if(ans==-1)
cout<<"background\n";
else
cout<<"window "<<ans+1<<'\n';
}
}
}

1. #include <cstdio>

int main() {