Cod sursa(job #354909)

Utilizator Mishu91Andrei Misarca Mishu91 Data 9 octombrie 2009 21:10:47
Problema Ograzi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <vector>

using namespace std;

#define MOD 6763
#define MAX_N 50005
#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 <int> G[MOD];
pair <int, int> V[MAX_N];

int hash(int x, int y)
{
	return (x * P1 + y) % MOD;
}

int find(int x, int y)
{
	int h1 = (2*x-1)/(2*W);
	int h2 = (2*y-1)/(2*H);

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

	foreach(G[p])
	{
		int i = *it;
		if(x >= V[i].x && x <= V[i].x+W && y >= V[i].y && y <= V[i].y+H)
			return 1;
	}

	return 0;
}

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

	for(int i = 1; i <= N; ++i)
	{
		fin >> V[i].x >> V[i].y;
		++V[i].x, ++V[i].y;

		int x = (2*V[i].x-1) / (2*W);
		int y = (2*V[i].y-1) / (2*H);

		G[hash(x,y)].push_back(i);
		G[hash(x+1,y)].push_back(i);
		G[hash(x+1,y+1)].push_back(i);
		G[hash(x,y+1)].push_back(i);
	}

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

		fin >> x >> y;
		++x, ++y;

		Sol += find(x, y);
	}

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