Cod sursa(job #26262)

Utilizator IgnitionMihai Moraru Ignition Data 5 martie 2007 13:22:09
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <vector>
#include <map>

using namespace std;

#define pb push_back
#define mp make_pair

int N, M, W, H, X;
vector< pair<int, int> > n;
map< pair<int, int>, int> hash;

inline int inside(pair<int, int> v1, pair<int, int> v2)
{
	if(v1.first <= v2.first && v2.first <= v1.first+W &&
	v1.second <= v2.second && v2.second <= v1.second+H)
		return 1;
	return 0;
}

int main()
{

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

	int i, a, b;
	scanf("%d %d %d %d", &N, &M, &W, &H);
	n.reserve(N);

	for(i = 0; i < N; ++ i) {
		scanf("%d %d", &a, &b); ++ a, ++ b;
		hash[mp(a/W, b/H)] = i;
		n.pb(mp(a, b));
	}

	for(X = i = 0; i < M; ++ i) {
		scanf("%d %d", &a, &b); ++ a; ++ b;
		int x = a/W, y = b/H;
		typeof(hash.begin()) it;

		if((it = hash.find(mp(x, y))) != hash.end())
			X += inside(n[it->second], mp(a, b));
		if((it = hash.find(mp(x-1, y))) != hash.end())
			X += inside(n[it->second], mp(a, b));
		if((it = hash.find(mp(x, y-1))) != hash.end())
			X += inside(n[it->second], mp(a, b));
		if((it = hash.find(mp(x-1, y-1))) != hash.end())
			X += inside(n[it->second], mp(a, b));
	}

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

	return 0;
}