Cod sursa(job #755602)

Utilizator GrimpowRadu Andrei Grimpow Data 6 iunie 2012 15:10:26
Problema Ograzi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define fin "ograzi.in"
#define fout "ograzi.out"
#define nmax 50005
#define hashmax 4194303

typedef struct pnod {
                  int i,j,pozdr;
                  pnod *next;
                  };
pnod *hash[hashmax];
int dr[nmax][2], n,m,w,h,rez;

int aflagrila(int x, int h );
void baga_hash(int x,int y,int i);
int cauta(int ,int j,int xx,int yy);
void citire();

int main()
{
citire();
return 0;
}

int aflagrila(int x,int h)
{
if ( x == 0) return 0;
return int( (x-0.5) /h ) + 1;
}


void baga_hash (int x,int y,int i)
{
pnod *p;
int poz;
poz = ( 11*x + 113*y) % hashmax;
p = new pnod;
p->i=x; p->j=y; p->pozdr = i; p->next = hash[poz];
hash[poz] = p;
}

int cauta(int i,int j,int xx,int yy)
{
int poz,d;
pnod *p;

if (i < 0 || j < 0) return 0;
poz = (11*i+113*j) % hashmax;
p=hash[poz];
while ( p != NULL )
      {
      if (p->i == i && p->j == j )
	 {
	 d = p->pozdr;
         if (xx >= dr[d][1] && xx<=dr[d][1]+w && yy >= dr[d][2] && yy<=dr[d][2]+h)
            return 1;
         }
     p=p->next;
     }
return 0;
}

void get(int &x1, int &x2)
{
int i,rez,l;
char str[50];
gets(str);
rez=0; i=0;
for (i=0; str[i] != ' '; i++)
	rez=rez*10 + int(str[i])-int('0');
i+=1;
x1=rez;
rez=0; l=strlen(str);
for (; i<l; i++)
	rez=rez*10 + int(str[i])-int('0');
x2=rez;
}

void citire()
{
int i,x,y,xx,yy,dxx,dyy;
freopen(fin,"r",stdin);
scanf("%d %d %d %d\n",&n,&m, &w,&h);
for (i=1; i<=n; i++)
    {
    //scanf("%d %d",&dxx,&dyy);
    get(dxx,dyy);
    dr[i][1]=dxx; dr[i][2]=dyy;
    x=aflagrila(dr[i][1],w);
    y=aflagrila(dr[i][2],h);
    baga_hash(x,y,i);
    }
for (i=1; i<=m; i++)
    {
    //scanf("%d %d",&xx,&yy);
    get(xx,yy);
    x=aflagrila(xx,w);
    y=aflagrila(yy,h);
    if (cauta(x,y,xx,yy)) rez+=1;
    if (cauta(x-1,y,xx,yy)) rez+=1;
    if (cauta(x,y-1,xx,yy)) rez+=1;
    if (cauta(x-1,y-1,xx,yy)) rez+=1;
    }
fclose(stdin);
freopen(fout,"w",stdout);
printf("%d",rez);
fclose(stdout);
}