Cod sursa(job #354898)

Utilizator Mishu91Andrei Misarca Mishu91 Data 9 octombrie 2009 20:38:58
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <vector>

using namespace std;

#define MOD 666013
#define P1 103

#define x first
#define y second

#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

ifstream fin ("ograzi.in");
ofstream fout ("ograzi.out");

int N, M, H, W, Sol;

vector < pair<int, int> > G[MOD];

void hash(int x, int y)
{
	int h1 = x/W;
	int h2 = y/H;

	if(x % W == 0) --h1;
	if(y % H == 0) --h2;

	int p = (h1*P1 + h2) % MOD;

	G[p].push_back(make_pair(x, y));
}

int find(int x, int y)
{
	int h1 = x/W;
	int h2 = y/H;

	if(x % W == 0) --h1;
	if(y % H == 0) --h2;

	int p = (h1*P1 + h2) % MOD;

	foreach(G[p])
		if(x >= it -> x && x <= it -> x+W && y >= it -> y && y <= it -> y+H)
			return 1;

	return 0;
}

int main()
{
	fin >> N >> M >> W >> H;

	for(int i = 1; i <= N; ++i)
	{
		int x, y;

		fin >> x >> y;
		hash(x+1, y+1);
		hash(x+1+W, y+1);
		hash(x+1+W, y+1+H);
		hash(x+1, y+1+H);
	}

	for(int i = 1; i <= M; ++i)
	{
		int x, y;

		fin >> x >> y;
		Sol += find(x+1, y+1);
	}

	fout << Sol << "\n";
}