Cod sursa(job #354919)

Utilizator Mishu91Andrei Misarca Mishu91 Data 9 octombrie 2009 21:33:12
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>
#include <vector>
#include <cstdlib>

using namespace std;

#define MOD 6763
#define MAX_N 50005
#define P1 103
#define DIM 8192

#define x first
#define y second

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

int N, M, H, W, Sol;
int pos = DIM-1;

char buf[DIM];

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

void read(int &x)
{
	x = 0;
	while(!isdigit(buf[pos]))
		if(++pos == DIM)
			fread(buf, sizeof(char), DIM, stdin), pos = 0;

	while(isdigit(buf[pos]))
	{
		x = x*10 + buf[pos] - '0';

		if(++pos == DIM)
			fread(buf, sizeof(char), DIM, stdin), pos = 0;
	}
}

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()
{
	freopen("ograzi.in","rt",stdin);
	freopen("ograzi.out","wt",stdout);

	read(N); read(M); read(W); read(H);

	for(int i = 1; i <= N; ++i)
	{
		read(V[i].x); read(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 a(0), b(0);

		read(a); read(b);
		++a, ++b;

		Sol += find(a, b);
	}
	
	printf("%d\n",Sol);
}