Mai intai trebuie sa te autentifici.
Cod sursa(job #28853)
Utilizator | Data | 8 martie 2007 13:20:22 | |
---|---|---|---|
Problema | Ograzi | Scor | 100 |
Compilator | c | Status | done |
Runda | Arhiva de probleme | Marime | 1.76 kb |
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MN (65536)
#define MOD (1048576)
int N, M, W, H, X;
int n[MN][2];
unsigned short hash_table[MOD][4];
inline unsigned fnv_hash ( void *key, int len )
{
unsigned char *p = key;
unsigned h = 2166136261U;
int i;
for(i = 0; i < len; ++i)
h = (h*16777619)^p[i];
return h;
}
inline unsigned hash_function(int x, int y)
{
unsigned tmp = ((x&0xFFFF) << 16) + (y&0xFFFF);
int h = fnv_hash(&tmp, 4)%MOD;
return h;
}
inline int inside(int x1, int y1, int x2, int y2)
{
return ((x1 <= x2 && x2 <= x1+W) && (y1 <= y2 && y2 <= y1+H));
}
int main()
{
freopen("ograzi.in", "r", stdin);
freopen("ograzi.out", "w", stdout);
int i, j, id, tmpid, mx, my;
char cc[16];
scanf("%d %d %d %d ", &N, &M, &W, &H);
for(i = 0; i < N; ++i) {
//scanf("%d %d", &n[i][0], &n[i][1]); ++ n[i][0]; ++ n[i][1];
fgets(cc, 15, stdin);
for(mx = j = 0; '0' <= cc[j] && cc[j] <= '9'; ++j)
mx *= 10, mx += cc[j]-'0';
for(my = 0, ++j; '0' <= cc[j] && cc[j] <= '9'; ++j)
my *= 10, my += cc[j]-'0';
n[i][0] = ++mx; n[i][1] = ++my;
tmpid = hash_function(mx/W, my/H);
hash_table[tmpid][++hash_table[tmpid][0]] = i;
}
int ox, oy, x, y;
const int dx[] = {0, -1, 0, -1}, dy[] = {0, 0, -1, -1};
for(X = 0; M--;) {
//scanf("%d %d", &mx, &my); ++mx; ++my;
fgets(cc, 15, stdin);
for(mx = j = 0; '0' <= cc[j] && cc[j] <= '9'; ++j)
mx *= 10, mx += cc[j]-'0';
for(my = 0, ++ j; '0' <= cc[j] && cc[j] <= '9'; ++j)
my *= 10, my += cc[j]-'0';
ox = (++mx)/W; oy = (++my)/H;
for(j = 0; j < 4; ++j) {
x = ox+dx[j]; y = oy+dy[j];
tmpid = hash_function(x, y);
for(i = 1; i <= hash_table[tmpid][0]; ++i) {
id = hash_table[tmpid][i];
X += inside(n[id][0], n[id][1], mx, my);
}
}
}
printf("%d\n", X);
return 0;
}