Cod sursa(job #49158)

Utilizator andrei_infoMirestean Andrei andrei_info Data 5 aprilie 2007 14:51:14
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define fin "ograzi.in"
#define fout "ograzi.out"
#define nmax 50005
#define hashmax 2500000

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 = ( 2*x + 7*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 = (2*i+7*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 citire()
{
int i,x,y,xx,yy,dxx,dyy;
freopen(fin,"r",stdin);
scanf("%d %d %d %d",&n,&m, &w,&h);
for (i=1; i<=n; i++)
    {
    scanf("%d %d",&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);
    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);
}