Cod sursa(job #150041)

Utilizator sealTudose Vlad seal Data 6 martie 2008 15:27:24
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
using namespace std;
#include<cstdio>
#include<vector>
#include<algorithm>
#define Hm 666013
#define f first
#define s second
int a,b;
vector< pair<int,int> > H[Hm];

inline int hash(int x, int y)
{
    x=(x*2-1)/(2*a); y=(y*2-1)/(2*b);
    return ((long long)x*y+x+y)%Hm;
}

inline bool check(int x, int y, int i)
{
    vector< pair<int,int> >::iterator it;

    for(it=H[i].begin();it!=H[i].end();++it)
        if(x>=it->f && x<=it->f+a && y>=it->s && y<=it->s+b)
            return 1;
    return 0;
}

int main()
{
    char S[16];
    int n,m,x,y,i;

    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);

    scanf("%d%d%d%d ",&n,&m,&a,&b);
    while(n--)
    {
        gets(S);
        for(x=i=0;S[i]!=' ';++i)
            x=x*10+S[i]-'0';
        for(y=0,++i;S[i];++i)
            y=y*10+S[i]-'0';
        H[hash(x+a,y+b)].push_back(make_pair(x,y));
    }

    n=0;
    while(m--)
    {
        gets(S);
        for(x=i=0;S[i]!=' ';++i)
            x=x*10+S[i]-'0';
        for(y=0,++i;S[i];++i)
            y=y*10+S[i]-'0';
        i=hash(x,y);
        if(check(x,y,i))
        {
            ++n;
            continue;
        }
        i=hash(x+a,y);
        if(check(x,y,i))
        {
            ++n;
            continue;
        }
        i=hash(x,y+b);
        if(check(x,y,i))
        {
            ++n;
            continue;
        }
        i=hash(x+a,y+b);
        if(check(x,y,i))
            ++n;
    }
    printf("%d\n",n);
    return 0;
}