Cod sursa(job #1238884)

Utilizator george_stelianChichirim George george_stelian Data 7 octombrie 2014 21:23:08
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>

using namespace std;

const int mod=666013;
struct punct
{
    int x,y;
}v[50010];
int v1[mod],nr,n,m,w,h,sol;
char pars[15000000];

int read()
{
    int x=0;
    for(;pars[nr]>='0' && pars[nr]<='9';nr++) x=x*10+pars[nr]-'0';
    nr++;
    return x;
}
int inc(int x)
{
    if(++x==mod) x=0;
    return x;
}
int normx(int x)
{
    return x/w+1;
}
int normy(int y)
{
    return y/h+1;
}
void hash_insert(int i)
{
    int a=(normx(v[i].x)*997+normy(v[i].y)*31)%mod;
    for(;v1[a];a=inc(a));
    v1[a]=i;
}
int hash_find(int x,int y)
{
    int a=(x*997+y*31)%mod;
    for(;v1[a] && (normx(v[v1[a]].x)!=x || normy(v[v1[a]].y)!=y);a=inc(a));
    return v1[a];
}

int main()
{
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    fread(pars,1,15000000,stdin);
    n=read();m=read();w=read();h=read();
    for(int i=1;i<=n;i++)
    {
        v[i].x=read();v[i].y=read();
        hash_insert(i);
    }
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        int x1=x/w+1,y1=y/h+1,a;
        a=hash_find(x1,y1);
        if(a && v[a].x<=x && v[a].x+w>=x && v[a].y<=y && v[a].y+h>=y) sol++;
        x1--;
        if(x1>0)
        {
            a=hash_find(x1,y1);
            if(a && v[a].x<=x && v[a].x+w>=x && v[a].y<=y && v[a].y+h>=y) sol++;
        }
        y1--;
        if(x1>0 && y1>0)
        {
            a=hash_find(x1,y1);
            if(a && v[a].x<=x && v[a].x+w>=x && v[a].y<=y && v[a].y+h>=y) sol++;
        }
        x1++;
        if(y1>0)
        {
            a=hash_find(x1,y1);
            if(a && v[a].x<=x && v[a].x+w>=x && v[a].y<=y && v[a].y+h>=y) sol++;
        }
    }
    printf("%d",sol);
    return 0;
}