Cod sursa(job #222242)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 21 noiembrie 2008 14:14:21
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <vector>

using namespace std;

#define MOD 666013
#define DIM 8192

int N, M, H, W, cnt;
vector <int> h[MOD];

struct punct
{
	int x, y;
} ograzi[50005];

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

char ax[DIM+16];
int pz;
inline void cit(int &x)
{
	x=0;
	while((ax[pz]<'0' || ax[pz]>'9') && (ax[pz]!='-'))
		if(++pz==DIM)fread(ax, 1, DIM, stdin), pz=0;

	
	int neg=0;
	if(ax[pz]=='-')
	{
		neg=1;
		if(++pz==DIM)fread(ax, 1, DIM, stdin),pz=0;
	}
	
	while(ax[pz]>='0' && ax[pz]<='9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz==DIM)fread(ax,1, DIM, stdin),pz=0;
	}
	if(neg) x=-x;
}

int verif(int x, int y, int p)
{
	if (x >= ograzi[p].x && x <= ograzi[p].x + W && y >= ograzi[p].y && y <= ograzi[p].y + H) return 1;
	return 0;
}

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

	int i, j, x, y;

	cit(N); cit(M); cit(W); cit(H);
	for (i = 1; i <= N; i++)
	{
		cit(ograzi[i].x); cit(ograzi[i].y);
		x = (2 * ograzi[i].x - 1) / (2 * W);
		y = (2 * ograzi[i].y - 1) / (2 * H);

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

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

		x = (2 * xx - 1) / (2 * W); 
		y = (2 * yy - 1) / (2 * H);
		int poz = hash(x,y);
		for (j = 0; j < h[poz].size(); j++) cnt += verif(xx,yy,h[poz][j]);
	}

	printf("%d\n",cnt);
	return 0;
}