Cod sursa(job #332251)

Utilizator freak93Adrian Budau freak93 Data 17 iulie 2009 10:15:01
Problema Ograzi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include<cstring>
#include<cstdio>

using namespace std;

const int maxn=50010;
const int mod=479909;
const int prime=104729;

int n,m,p=1024,w,h,points;

char s[1024];

void cit(int &x)
{
    x=0;
    if(p==1024)
        fread(s,1,1024,stdin),p=0;
    while(s[p]<'0'||s[p]>'9')
    {
        ++p;
        if(p==1024)
            fread(s,1,1024,stdin),p=0;
    }

    while(s[p]>='0'&&s[p]<='9')
    {
        x=(x>>1)+(x>>3)+s[p]-'0';
        ++p;
        if(p==1024)
            fread(s,1,1024,stdin),p=0;
    }
}

struct punct
{
    int x,y;
}a[maxn];

struct nod
{
    long long v;
    int drept;
    nod *next;
}*hash[mod];

void insert(int x,int y,int drept)
{
    nod *k=new nod;
    k->v=x*prime+y;
    k->drept=drept;
    long long list=k->v%mod;
    k->next=hash[list];
    hash[list]=k;
}

bool is_in(int x,int y,int xs,int ys)
{
    nod *i;
    long long list=xs*prime+ys,v;
    v=list;
    list%=mod;
    for(i=hash[list];i;i=i->next)
        if(i->v==v)
            break;
    if(i==0)
        return false;
    int drept=i->drept;
    if(a[drept].x<=x&&a[drept].y<=y&&a[drept].x+w>x&&a[drept].y+h>y)
        return true;
    return false;
}

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

    int x,y,xs,ys,i;
    for(i=1;i<=n;++i)
    {
        cit(x);
        cit(y);
        xs=x%(w+1);
        ys=y%(h+1);
        if(xs)
            xs=x+w+1-xs;
        else
            xs=x;
        if(ys)
            ys=y+h+1-ys;
        else
            ys=y;
        a[i].x=x;
        a[i].y=y;
        insert(xs,ys,i);
    }

    for(i=1;i<=m;++i)
    {
        cit(x);
        cit(y);
        xs=x%(w+1);
        ys=y%(h+1);
        if(xs)
            xs=x+w+1-xs;
        else
            xs=x;
        if(ys)
            ys=y+h+1-ys;
        else
            ys=y;
        if(is_in(x,y,xs,ys)||is_in(x,y,xs-w-1,ys-h-1)||is_in(x,y,xs-w-1,ys)||is_in(x,y,xs,ys-h-1))
            ++points;
    }

    printf("%d\n",points);
    return 0;
}