zoj3664长春J

gistfile1.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define NN 2100

int xl,yl,xr,yr,root,totnode,n,q,i,pos,dep,tmp1,tmp2,ans,son[NN];

struct node{
    int l,r;
    int fa,dep;
    int xl,yl,xr,yr;
    void init(int de,int f){
        l=r=0;
        dep=de;
        fa=f;
    }
    void update(int a,int b,int c,int d){
        xl=a;yl=b;xr=c;yr=d;
    }
}nd[NN];

int find(int root,int x,int y){
    int tmp=root,tt;
    while(1){
        if (nd[tmp].l==0) return tmp;
        tt=nd[tmp].l;
        if (x<=nd[tt].xr&&x>=nd[tt].xl&&y>=nd[tt].yl&&y<=nd[tt].yr){tmp=tt;}
        else tmp=nd[tmp].r;
    }
    printf("fuck!!\n");
}

int getson(int now){
     son[now]=0;
     if (nd[now].l){
         son[now]+=getson(nd[now].l);
         son[now]+=getson(nd[now].r);
     }
     return son[now]+1;
}



int main(){
    while(scanf("%d%d%d%d",&xl,&yl,&xr,&yr)!=EOF){
        totnode=1;
        root=1;
        nd[1].init(0,-1);
        nd[1].update(xl,yl,xr,yr);
        
        scanf("%d%d",&n,&q);
        for(i=1;i<=n;i++){
            scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
            if (xl>xr) swap(xl,xr);
            if (yl>yr) swap(yl,yr);
            pos=find(1,(xl+xr)/2,(yl+yr)/2);
            dep=nd[pos].dep;
            
            nd[pos].l=++totnode;
            nd[totnode].init(dep+1,pos);
            nd[totnode].update(nd[pos].xl,nd[pos].yl,xr,yr);
            nd[pos].r=++totnode;
            nd[totnode].init(dep+1,pos);
            nd[totnode].update(xl,yl,nd[pos].xr,nd[pos].yr);
        }
        getson(1);
        for(i=1;i<=q;i++){
            scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
            tmp1=find(1,xl,yl);
            tmp2=find(1,xr,yr);
            //printf("%d  %d\n",tmp1,tmp2);
            ans=0;
            
            while(tmp1!=tmp2){
               if (nd[tmp1].dep>nd[tmp2].dep) {tmp1=nd[tmp1].fa;}
               else if (nd[tmp1].dep<nd[tmp2].dep) {tmp2=nd[tmp2].fa;}
               else {tmp1=nd[tmp1].fa;tmp2=nd[tmp2].fa;}
            }
            ans=son[tmp1];
            printf("%d\n",n+1-ans/2);
        }
    }
    return 0;
}