Pagini recente » Cod sursa (job #206530) | Cod sursa (job #1225114) | Profil gosu_gamer | Cod sursa (job #365217) | Cod sursa (job #27019)
Cod sursa(job #27019)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define dim_hash 100000
#define formula (sqrt(5)-1)/2
#define nmax 50000
long n, m, w, h, hash[dim_hash][60], 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,25,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,14,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,14,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;
}