Cod sursa(job #26643)

Utilizator vrajalaMihai Viteazu, razboinicu luminii vrajala Data 5 martie 2007 20:02:15
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define dim_hash 10000
#define formula (sqrt(5)-1)/2
#define nmax 50000

long n, m, w, h, hash[dim_hash][20], key, x[nmax], y[nmax], ox, oy, nr, k;
FILE *f;

void add_hash(long x,long y)
{
long xx,yy;
double pfrac;
xx=(x/w)+1;
yy=(y/h)+1;
pfrac=(formula*(xx+yy))-floor(formula*(xx+yy));
key=floor(pfrac*dim_hash);
++hash[key][0];
hash[key][hash[key][0]]=k;
}

void get_hash(long ox, long oy)
{
double xx,yy,pfrac;
long i;
xx=((ox)/w)+1;
yy=((oy)/h)+1;
pfrac=(formula*(xx+yy))-floor(formula*(xx+yy));
key=floor(pfrac*dim_hash);
for (i=1;i<=hash[key][0];++i)
    if ((x[hash[key][i]]<=ox)&&(ox<=x[hash[key][i]]+w)&&(y[hash[key][i]]<=oy)&&(oy<=y[hash[key][i]]+h))
       {
	++nr;
	return;
       }
xx=+1;
pfrac=(formula*(xx+yy))-floor(formula*(xx+yy));
key=floor(pfrac*dim_hash);
for (i=1;i<=hash[key][0];++i)
    if ((x[hash[key][i]]<=ox)&&(ox<=x[hash[key][i]]+w)&&(y[hash[key][i]]<=oy)&&(oy<=y[hash[key][i]]+h))
       {
	++nr;
	return;
       }
yy+=1;
pfrac=(formula*(xx+yy))-floor(formula*(xx+yy));
key=floor(pfrac*dim_hash);
for (i=1;i<=hash[key][0];++i)
    if ((x[hash[key][i]]<=ox)&&(ox<=x[hash[key][i]]+w)&&(y[hash[key][i]]<=oy)&&(oy<=y[hash[key][i]]+h))
       {
	++nr;
	return;
       }
xx-=1;
pfrac=(formula*(xx+yy))-floor(formula*(xx+yy));
key=floor(pfrac*dim_hash);
for (i=1;i<=hash[key][0];++i)
    if ((x[hash[key][i]]<=ox)&&(ox<=x[hash[key][i]]+w)&&(y[hash[key][i]]<=oy)&&(oy<=y[hash[key][i]]+h))
       {
	++nr;
	return;
       }
}

void citire()
{
char s[40];
int i=0;
f=fopen("ograzi.in","r");
fgets(s,30,f);
while (s[i]!=' ')
      {
       n=n*10+(s[i++]-'0');
      }
      ++i;
while (s[i]!=' ')
      {
       m=m*10+(s[i++]-'0');
      }
      ++i;
while (s[i]!=' ')
      {
       w=w*10+(s[i++]-'0');
      }
      ++i;
while (s[i]!='\n')
      {
       h=h*10+(s[i++]-'0');
      }
for (k=0;k<n;++k)
    {
     fgets(s,30,f);
     i=0;
     while (s[i]!=' ')
      {
       x[k]=x[k]*10+(s[i++]-'0');
      }
      ++i;
      while (s[i]!='\n')
      {
       y[k]=y[k]*10+(s[i++]-'0');
      }
      add_hash(x[k],y[k]);
    }
for (k=0;k<m;++k)
    {
     fgets(s,30,f);
     i=0;
     ox=0;
     oy=0;
     while (s[i]!=' ')
      {
       ox=ox*10+(s[i++]-'0');
      }
      ++i;
      while (s[i]!='\n')
      {
       oy=oy*10+(s[i++]-'0');
      }
      get_hash(ox,oy);
    }
fclose(f);
}

void citire2()
{
f=fopen("ograzi.in","r");
fscanf(f,"%ld %ld %ld %ld\n",&n,&m,&w,&h);
for (k=0;k<n;++k)
    {
     fscanf(f,"%ld %ld\n",&x[k],&y[k]);
     add_hash(x[k],y[k]);
    }
for (k=0;k<m;++k)
    {
    fscanf(f,"%ld %ld\n",&ox,&oy);
    get_hash(ox,oy);
    }
fclose(f);
}

int main()
{
      citire();
      f=fopen("ograzi.out","w");
      fprintf(f,"%ld",nr);
      fclose(f);
      return 0;
}