Cod sursa(job #28753)

Utilizator IgnitionMihai Moraru Ignition Data 8 martie 2007 11:18:16
Problema Ograzi Scor 60
Compilator c Status done
Runda Arhiva de probleme Marime 2.6 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 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 oat_hash ( void *key, int len )
{
	unsigned char *p = key;
	unsigned h = 0;
	int i;

	for ( i = 0; i < len; i++ ) {
		h += p[i];
		h += ( h << 10 );
		h ^= ( h >> 6 );
	}

	h += ( h << 3 );
	h ^= ( h >> 11 );
	h += ( h << 15 );

	return h;
}
*/

inline unsigned hash_function(int x, int y)
{
	//unsigned long long tmp = ((long long)x << 32)+y;
	unsigned tmp = ((x&0xFFFF) << 16) + (y&0xFFFF);
	int h = fnv_hash(&tmp, sizeof(tmp))%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()
{
	/*
	printf("******************* %10d\n", MOD);
	memset(hash_table, 0, sizeof(hash_table));
	int i, id, a, b, total = 0, collisions = 0, incol = 0, maxcol = 0;
	for(a = 0; a < 1000; ++a) for(b = 0; b < 1000; ++b) {
		id = hash_function(a, b);
		hash_table[id][++hash_table[id][0]] = a*1000+b;
	}

	for(a = 0; a < MOD; ++a) {
		if(hash_table[a][0] > 1) {
			++collisions;
			incol += hash_table[a][0];
			if(hash_table[a][0] > maxcol)
				maxcol = hash_table[a][0];
			if(hash_table[a][0] == maxcol) {
				printf("%d: ", a);
				for(i = 1; i <= hash_table[a][0]; ++i) {
					int tmp = hash_table[a][i], x, y;
					x = tmp/1000;
					y = tmp-(x*1000);
					printf(" %d,%d", x, y);
				}
				printf("\n");
			}
			//printf("%d %d\n", a, hash_table[a]);
		}
		total += hash_table[a][0];
	}
	printf("total %d\n", total);
	printf("collisions %d\n", collisions);
	printf("incol %d\n", incol);
	printf("maxcol %d\n", maxcol);

	return 0;
	*/

	freopen("ograzi.in", "r", stdin);
	freopen("ograzi.out", "w", stdout);

	int i, j, id, tmpid, mx, my;
	//memset(hash_table, 0, sizeof(hash_table));
	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];
		tmpid = hash_function(n[i][0]/W, n[i][1]/H);
		hash_table[tmpid][++hash_table[tmpid][0]] = i;
	}

	for(X = 0; M--;) {
		scanf("%d %d", &mx, &my); ++mx; ++my;
		int ox = mx/W, oy = my/H, dx[] = {0, -1, 0, -1}, dy[] = {0, 0, -1, -1}, x, y;

		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;
}