Cod sursa(job #1419563)

Utilizator livliviLivia Magureanu livlivi Data 15 aprilie 2015 22:44:22
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<algorithm>
#include<cstdio>
#define N 50000
#define mod 251063
#define M 997
using namespace std;

struct punct{
    int x,y;
};


punct d[N+1];
int urm[N+1];
int lst[mod];
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;
}


void adauga(int i){
    int key=(d[i].x/w*M+d[i].y/h)%mod;
    urm[i]=lst[key];
    lst[key]=i;
}


bool cauta(punct p){
    int key;
    int i;
    int m1,m2;

    for(m1=-1;m1<=0;m1++)
        for(m2=-1;m2<=0;m2++){
            key=((p.x/w+m1)*M+p.y/h+m2)%mod;

            if (key>=0) i=lst[key];
            else i=0;
            while(i!=0){
                if (p.x>=d[i].x &&p.x<=d[i].x+w &&p.y>=d[i].y &&p.y<=d[i].y+h) return true;
                i=urm[i];
            }
        }

    return false;
}


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

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

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

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

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