Cod sursa(job #28658)

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

#define MN (65536)
//#define MM (100009)
#define MOD (1048576)

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 = 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("%d\n", 0xFFFF); return 0;

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

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