Cod sursa(job #2273726)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 31 octombrie 2018 21:12:46
Problema Ograzi Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.41 kb
#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

#define dim_hash 50000

#define formula (sqrt(5)-1)/2

#define nmax 50000



long n, m, w, h, hash[dim_hash][120], 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);

key=(2*xx+3*yy) % dim_hash;

++hash[key][0];

hash[key][hash[key][0]]=k;

}



void get_hash(long ox, long oy)

{

long xx,yy;

double pfrac;

long i;

xx=(ox/w)+1;

yy=(oy/h)+1;

//pfrac=(formula*(xx+yy))-floor(formula*(xx+yy));

//key=floor(pfrac*dim_hash);

key = (2*xx+3*yy) % 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);

key = (2*xx+3*yy) % 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);

key = (2*xx+3*yy) % 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);

key = (2*xx+3*yy) % 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;

int l;

f=fopen("ograzi.in","r");

fgets(s,40,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,20,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,20,f);

     l=strlen(s);

     i=0;

     ox=0;

     oy=0;

     while (s[i]!=' ')

      {

       ox=ox*10+(s[i++]-'0');

      }

      ++i;

      while ((i<l)&&(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;

}