Cod sursa(job #1812408)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 22 noiembrie 2016 01:33:40
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <cstdio>
#include <map>

using namespace std;

const int buffer=1<<18,mod=500000,prim1=103,prim2=223;

struct punct
{
    int x,y;
};

struct punct1
{
    int x,y,x1,y1,t;
};

const punct aux[4]={{0,0},{-1,0},{0,-1},{-1,-1}};
map<punct,punct> q;
int w,h,poz;
char pars[buffer];
punct1 hashh[mod+2];

int inclus(int x,int y,int a,int b)
{
    if(x>=a && x<=a+w && y>=b && y<=b+h) return 1;
    else return 0;
}

void inc()
{
    if(++poz==buffer)
    {
        poz=0;
        fread(pars,1,buffer,stdin);
    }
}

int read()
{
    for(;pars[poz]<'0' or '9'<pars[poz];inc());
    int s=0;
    for(;'0'<=pars[poz] && pars[poz]<='9';inc()) s=s*10+pars[poz]-'0';
    return s;
}

void hash_add(punct a,punct b)
{
    int i=(a.x*prim1+a.y*prim2)%mod;
    while(hashh[i].t!=0)
    {
        i++;
        if(i==mod) i=0;
    }
    hashh[i]={a.x,a.y,b.x,b.y,1};
}

punct hash_find(int a,int b)
{
    int i=(a*prim1+b*prim2)%mod;
    while(1)
    {
        if(hashh[i].t==0) return {-1,-1};
        if(hashh[i].x==a && hashh[i].y==b) return {hashh[i].x1,hashh[i].y1};
        i++;
        if(i==mod) i=0;
    }
}

int main()
{
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);
    int n,m,sol=0,x,y;
    fread(pars,1,buffer,stdin);
    n=read();m=read();w=read();h=read();
    for(int i=1;i<=n;i++)
    {
        x=read();y=read();
        hash_add({x/w,y/h},{x,y});
    }
    for(int i=1;i<=m;i++)
    {
        x=read();y=read();
        int a=x/w,b=y/h;
        for(int j=0;j<4;j++)
        {
            int x1=a+aux[j].x,y1=b+aux[j].y;
            punct p=hash_find(x1,y1);
            if(p.x!=-1) sol+=inclus(x,y,p.x,p.y);
        }
    }
    printf("%d",sol);
    return 0;
}