Cod sursa(job #1005019)

Utilizator andrettiAndretti Naiden andretti Data 3 octombrie 2013 22:21:44
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define H 123457
#define MOD 666013
#define maxb 8192
using namespace std;

#define NXT if(++pos==maxb) fread(buff,1,maxb,stdin),pos=0;
int n,m,w,h,sol;
int dx[4]={-1,0,-1,0},dy[4]={0,-1,-1,0};
vector< pair<int,int> > l[MOD];
char buff[maxb];
int pos=0;

int get_int()
{
    int nr=0;
    while(buff[pos]<'0' || buff[pos]>'9') NXT
    while(buff[pos]>='0' && buff[pos]<='9'){
        nr=nr*10+buff[pos]-'0';
        NXT
    }
    return nr;
}

int hash_key(int i,int j){
    return (1LL*i*H+j)%MOD;
}

void insert(int i,int j)
{
    int k=hash_key(i/w,j/h);
    l[k].pb(mp(i,j));
}

int search(int i,int j,int ind)
{
    int k=hash_key(i/w+dx[ind],j/h+dy[ind]);
    for(unsigned int it=0;it<l[k].size();it++)
     if(l[k][it].x<=i && i<=l[k][it].x+w && l[k][it].y<=j && j<=l[k][it].y+h)
      return 1;
    return 0;
}

void read()
{
    int xc,yc;
    n=get_int(); m=get_int();
    w=get_int(); h=get_int();
    for(int i=1;i<=n;i++)
    {
        xc=get_int(); yc=get_int();
        insert(xc,yc);
    }
}

void solve()
{
    int xc,yc;
    for(int i=1;i<=m;i++)
    {
        xc=get_int(); yc=get_int();
        for(int j=0;j<4;j++)
        {
            if(xc/w+dx[j]<0 || yc/h+dy[j]<0) continue;
            if(search(xc,yc,j)){
                sol++; break;
            }
        }
    }
}

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

    read();
    solve();
    printf("%d",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}