Pagini recente » Cod sursa (job #2370532) | Cod sursa (job #1264117) | Cod sursa (job #87774) | Cod sursa (job #2115175) | Cod sursa (job #26643)
Cod sursa(job #26643)
#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;
}