Cod sursa(job #85258)

Utilizator devilkindSavin Tiberiu devilkind Data 20 septembrie 2007 17:56:07
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <stdio.h>
#include <string.h>
#define modulo 666013

struct hash{long int x,y,px,py;
            hash *urm;} *vf[modulo],*p;

long int n,m,i,j,k,h,w,x,y,x1,y1,px,py,val,ok,sol;
char s[100];

inline long int funct(long int x, long int y)
{
return  ( (long long) x*y ) % modulo;
}


int verifica(long int x, long int y, long int px, long int py)
{
val=funct(px,py);
for (p=vf[val];p;p=p->urm)
          if ((p->px==px)&&(p->py==py))
                      if ((p->x<=x)&&(p->y<=y)&&(p->x+h>=x)&&(p->y+w>=y)) return 1;
return 0;
}



int main()
{

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

scanf("%ld %ld %ld %ld\n",&n,&m,&h,&w);
for (i=1;i<=n;i++)
        {
//        scanf("%ld %ld",&x,&y);
        
        fgets(s,100,stdin);
        x=y=0;
        for (j=0;s[j]!=' ';j++) x=x*10+s[j]-'0';
        for (j=j+1;s[j]!='\n';j++) y=y*10+s[j]-'0';
        
        x1=x/h;
        y1=y/w;

        if (x1*h==x) px=x1;
                else px=x1+1;
        if (y1*w==y) py=y1;
                else py=y1+1;

        val=funct(px,py);

        p=new hash;
        p->px=px;
        p->py=py;
        p->x=x;
        p->y=y;
        p->urm=vf[val];
        vf[val]=p;
        }

for (i=1;i<=m;i++)
        {

//        scanf("%ld %ld",&x,&y);

        fgets(s,100,stdin);
        x=y=0;
        for (j=0;s[j]!=' ';j++) x=x*10+s[j]-'0';
        for (j=j+1;s[j]!='\n';j++) y=y*10+s[j]-'0';

        px=x/h;
        if (px*h==x) px--;
        py=y/w;
        if (py*w==y) py--;

        val=funct(px,py);

        ok=verifica(x,y,px,py);
        if (ok) {sol++;continue;}

        ok=verifica(x,y,px+1,py);
        if (ok) {sol++;continue;}

        ok=verifica(x,y,px,py+1);
        if (ok) {sol++;continue;}

        ok=verifica(x,y,px+1,py+1);
        if (ok) {sol++;continue;}

        ok=verifica(x,y,px-1,py-1);
        if (ok) {sol++;continue;}

        ok=verifica(x,y,px,py-1);
        if (ok) {sol++;continue;}

        ok=verifica(x,y,px-1,py);
        if (ok) {sol++;continue;}

        ok=verifica(x,y,px+1,py-1);
        if (ok) {sol++;continue;}

        ok=verifica(x,y,px-1,py+1);
        if (ok) {sol++;continue;}           
        }
printf("%ld",sol);
return 0;
}