Cod sursa(job #28840)

Utilizator IgnitionMihai Moraru Ignition Data 8 martie 2007 13:13:03
Problema Ograzi Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.75 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][5];

inline unsigned bernstein(void *key, int len)
{
	unsigned char *p = key;
	unsigned h = 0;

	int i;
	for(i = 0; i < len; ++i)
		h = 33*h + p[i];
	return h;
}

inline unsigned hash_function(int x, int y)
{
	unsigned tmp = ((x&0xFFFF) << 16) + (y&0xFFFF);
	int h = bernstein(&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;
}