Cod sursa(job #1419548)

Utilizator livliviLivia Magureanu livlivi Data 15 aprilie 2015 22:01:40
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include<algorithm>
#include<cstdio>
#define N 50000
using namespace std;

struct punct{
    int x,y;
};

struct dreptunghi{
    int v[4];
    int x,y;
};

punct ogr[N+1];
dreptunghi d[N*4+1];
int w,h,n;

char s[20];

punct get(){
    int j=0;
    punct p;
    gets(s);

    p.x=0;
    while(s[j]!=' '){
        p.x=p.x*10+s[j]-'0';
        j++;
    }

    j++;
    p.y=0;
    while(s[j]!=NULL){
        p.y=p.y*10+s[j]-'0';
        j++;
    }

    return p;
}


bool meow(dreptunghi a,dreptunghi b){
    if (a.x<b.x) return true;
    if (a.x==b.x &&a.y<b.y) return true;
    return false;
}


void add(int i,int j){
    if (d[j].v[0]!=0) d[i].v[0]=d[j].v[0];
    else
    if (d[j].v[1]!=0) d[i].v[1]=d[j].v[1];
    else
    if (d[j].v[2]!=0) d[i].v[2]=d[j].v[2];
    else d[i].v[3]=d[j].v[3];
}


int cb(punct pct){
    int poz,pas;

    pas=(1<<17);
    poz=0;

    pct.x=pct.x/w+1;
    pct.y=pct.y/h+1;

    while(pas>0){
        if (poz+pas<n &&d[poz+pas].x<pct.x) poz+=pas;
        pas>>=1;
    }

    pas=(1<<17);

    while(pas>0){
        if (poz+pas<n &&d[poz+pas].x==pct.x &&d[poz+pas].y<pct.y) poz+=pas;
        pas>>=1;
    }

    return poz;
}


bool ap(punct p,int i){
    if (d[i].v[0]!=0){
        if (p.x<=ogr[d[i].v[0]].x+w &&p.y<=ogr[d[i].v[0]].y+h) return true;
    }
    else
    if (d[i].v[1]!=0){
        if (p.x<=ogr[d[i].v[1]].x+w &&p.y>=ogr[d[i].v[1]].y) return true;
    }
    else
    if (d[i].v[2]!=0){
        if (p.x>=ogr[d[i].v[2]].x &&p.y>=ogr[d[i].v[2]].y) return true;
    }
    else
    if (d[i].v[3]!=0){
        if (p.x>=ogr[d[i].v[3]].x &&p.y<=ogr[d[i].v[3]].y+h) return true;
    }
    return false;
}


int main(){
    freopen ("ograzi.in","r",stdin);
    freopen ("ograzi.out","w",stdout);
    int m,i,j,aux,cnt;
    punct p;

    scanf ("%d%d%d%d\n",&n,&m,&w,&h);

    j=0;
    for(i=1;i<=n;i++){
        //scanf ("%d%d",&ogr[i].x,&ogr[i].y);
        ogr[i]=get();

        j++;
        d[j].v[2]=i;
        d[j].x=ogr[i].x/w+1;
        d[j].y=ogr[i].y/h+1;

        j++;
        d[j].v[1]=i;
        d[j].x=ogr[i].x/w+2;
        d[j].y=ogr[i].y/h+1;

        j++;
        d[j].v[3]=i;
        d[j].x=ogr[i].x/w+1;
        d[j].y=ogr[i].y/h+2;

        j++;
        d[j].v[0]=i;
        d[j].x=ogr[i].x/w+2;
        d[j].y=ogr[i].y/h+2;
    }

    sort(d+1,d+n*4+1,meow);

    j=1;
    for(i=2;i<=n*4;i++){
        if (d[i].x==d[j].x &&d[i].y==d[j].y) add(j,i);
        else {
            j++;
            d[j]=d[i];
        }
    }

    n=j;
    cnt=0;
    for(i=1;i<=m;i++){
        //scanf ("%d%d",&p.x,&p.y);
        p=get();
        aux=cb(p)+1;

        if (d[aux].x==p.x/w+1 &&d[aux].y==p.y/h+1)
            if (ap(p,aux)) cnt++;
    }

    printf ("%d",cnt);
    return 0;
}