CSP 窗口

原题链接

窗口

思路

给定一个点,很容易判断是否属于某个窗口。在这里,用结构体存放窗口的信息,包括窗口id和窗口排列的优先级,用z值的大小表示,z值越大,就越排在vector的前面。
从最上面的窗口开始判断点击的位置是否属于该窗口,一旦查询到属于某个窗口,则将该窗口的z值变成最大的。这里用++n保证,最新点击的z值是最大的。

代码

#include <bits/stdc++.h>
using namespace std;

struct node{
    int id; 
    int x1,y1,x2,y2;
    int z;//z值越大,则越靠前 
    node(int i,int x11,int y11,int x22,int y22,int zz){
        id = i;
        x1 = x11;
        y1 = y11;
        x2 = x22;
        y2 = y22;
        z  = zz;
    }
};
bool cmp(const node&a,const node &b){
    return a.z>b.z;
}
bool isIn(int x,int y,node w){
    //判断(x,y)是否在w窗口中 
    if(x >= w.x1 && x <= w.x2 && y >= w.y1 && y <= w.y2){
        return true;
    }
    return false;
}
int main(){
    vector<node> v;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        v.push_back(node{i,x1,y1,x2,y2,i});
    } 
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        sort(v.begin(),v.end(),cmp);//每次都保证z大的在最上面 
        bool isfind = false;
        for(int i=0;i<v.size();i++){
            if(isIn(x,y,v[i])){
                //在某个窗口上
                v[i].z = ++n; //优先级加一 
                cout<<v[i].id<<endl;
                isfind = true;
                break ; 
            } 
        }
        if(isfind == false){
            cout<<"IGNORED"<<endl;
        }       
    }

}
Tags:

Add a Comment

邮箱地址不会被公开。