首页 > 代码库 > CCF (HLJU 1180)点击窗口 (模拟)

CCF (HLJU 1180)点击窗口 (模拟)

1180: 点击窗口

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 10  Solved: 3
[Submit][Status][Web Board]

Description

        在某图形操作系统中,有 N 个窗口,每个窗口都是一个两边与坐标轴分别平行的矩形区域。窗口的边界上的点也属于该窗口。窗口之间有层次的区别,在多于一个窗口重叠的区域里,只会显示位于顶层的窗口里的内容。
当你点击屏幕上一个点的时候,你就选择了处于被点击位置的最顶层窗口,并且这个窗口就会被移到所有窗口的最顶层,而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口,则系统会忽略你这次点击。
现在我们希望你写一个程序模拟点击窗口的过程。

Input

输入包含多组数据,以文件尾为结束。
数据的第一行有两个正整数,即 N 和 M。(1 ≤ N ≤ 30,1 ≤ M ≤ 30)
接下来 N 行按照从最下层到最顶层的顺序给出 N 个窗口的位置。 每行包含四个非负整数 x1, y1, x2, y2,表示该窗口的一对顶点坐标分别为 (x1, y1) 和 (x2, y2)。保证 x1 < x2,y1<y2
接下来 M 行每行包含两个非负整数 x, y,表示一次鼠标点击的坐标。
题目中涉及到的所有点和矩形的顶点的 x, y 坐标不超过 10000。

Output

输出包括 M 行,每一行表示一次鼠标点击的结果。如果该次鼠标点击选择了一个窗口,则输出这个窗口的编号(窗口按照输入中的顺序从 1 编号到 N);如果没有,则输出"IGNORED"(不含双引号)。

Sample Input

3 4
0 0 4 4
1 1 5 5
2 2 6 6
1 1
0 0
4 4
0 5

Sample Output

2
1
1
IGNORED



解析:模拟电脑窗口的点击过程。其实只需要用结构体存一下各个窗口的初始编号和区域位置,然后每次点击,从当前最上面一层开始往下扫描,点击的点第一次落在的区域所在窗口,就是所点击到的窗口,这时候把该窗口的初始编号输出,然后再把该窗口调整到最上面,对应程序也就是把当前窗口的结构体移动到结构体数组的最前面,再把他前面的结构体往后串。重复以上操作,m次结束即可。




AC代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef struct node{
    int x1, y1, x2, y2;
}Node;
Node node[32];                //窗口结构体数组
int a[32];                    //保存各个窗口的上下关系

int main(){
//    freopen("in.txt", "r", stdin);
    int n, m, x, y;
    while(scanf("%d%d", &n, &m)!=EOF){
        memset(a, 0, sizeof(a));
        memset(node, 0, sizeof(node));
        for(int i=1; i<=n; i++)
            scanf("%d%d%d%d", &node[i].x1, &node[i].y1, &node[i].x2, &node[i].y2);
        for(int i=1; i<=n; i++) a[i] = n-i+1;
        for(int i=0; i<m; i++){
            scanf("%d%d", &x, &y);
            int flag = 0;
            for(int j=1; j<=n; j++){
                int foo = a[j];
                if(x >= node[foo].x1 && x <= node[foo].x2 && y >= node[foo].y1 && y <= node[foo].y2){      //如果点击的位置落在该窗口
                    printf("%d\n", foo);
                    flag = 1;
                    for(int k=j; k>=2; k--) a[k] = a[k-1];            //调整各窗口相对上下位置
                    a[1] = foo;
                    break;
                }
            }
            if(!flag) puts("IGNORED");
        }
    }
    return 0;
}



体会:其实这题大一的时候时候就见过,只不过当时太水了,没能写出来,而且开始的时候想了一个不动脑子的方法,保存所有屏幕的窗口编号,按重叠关系,把它们标号,但是结果却超内存了。后来才想到这样做的~~~



CCF (HLJU 1180)点击窗口 (模拟)