Cod sursa(job #28618)

Utilizator IgnitionMihai Moraru Ignition Data 8 martie 2007 09:16:05
Problema Ograzi Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <stdio.h>
#include <string.h>
#include <math.h>

#define MN (50009)
#define MM (100009)
#define MOD (16777216)

int N, M, W, H, X;
int n[MN][2], m[2];
short int hash_table[MOD];

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

	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;
	int h = fnv_hash(&tmp, sizeof(tmp))%MOD;
	return h;
}

inline int inside(int x1, int y1, int x2, int y2)
{
	if((x1 <= x2 && x2 <= x1+W) && (y1 <= y2 && y2 <= y1+H))
		return 1;
	return 0;
}

int main()
{

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

	int i;
	memset(hash_table, -1, 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];
		hash_table[hash_function(n[i][0]/W, n[i][1]/H)] = i;
	}

	for(X = i = 0; i < M; ++ i) {
		scanf("%d %d", &m[0], &m[1]); 
		//printf("%d %d -> ", m[0], m[1]);
		++ m[0]; ++ m[1];
		int x = m[0]/W, y = m[1]/H, id;

		id = hash_table[hash_function(x, y)];
		//printf("%d ", id);
		X += (id != -1) && inside(n[id][0], n[id][1], m[0], m[1]);

		id = hash_table[hash_function(x-1, y)];
		//printf("%d ", id);
		X += (id != -1) && inside(n[id][0], n[id][1], m[0], m[1]);

		id = hash_table[hash_function(x, y-1)];
		//printf("%d ", id);
		X += (id != -1) && inside(n[id][0], n[id][1], m[0], m[1]);

		id = hash_table[hash_function(x-1, y-1)];
		//printf("%d ", id);
		X += (id != -1) && inside(n[id][0], n[id][1], m[0], m[1]);

		//printf("%10d\n", X);
		//printf("%d %d -> %d\n", m[0]-1, m[1]-1, X);
	}

	printf("%d\n", X);

	return 0;
}