Cod sursa(job #27301)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 6 martie 2007 12:22:25
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#include <map>

using namespace std;

#define MAXN 50005

int x[MAXN], y[MAXN];

//impartim planu in dreptunghiuri HxW, formand un grid
//fiecarei ograzi va contine doar un singur punct in grid
//pentru ograzile cu coordonatele divizibile cu H, respectiv V luam punctul din stanga jos

int N, M, H, W;
map< pair<int, int>, int > Mp;

pair<int, int> getPoint( int id )
{
	return make_pair( x[id] + (W - x[id] % W) % W, y[id] + (H - y[id] % H) % H);
}

int isin( int a, int b, int id )
{
	return (x[id] <= a && a <= x[id] + W) && (y[id] <= b && b <= y[id] + H);
}

int main()
{
	freopen("ograzi.in", "rt", stdin);
	freopen("ograzi.out", "wt", stdout);

	scanf("%d %d %d %d", &N, &M, &W, &H);

	for (int i = 0; i < N; i++)
	{
		scanf("%d %d", x + i, y + i);
		Mp[ getPoint(i) ] = i;
	}

	int NR = 0;

	for (; M; M--)
	{
		int a, b, A, B;
		scanf("%d %d", &a, &b);

		A = a - (a % W);
		B = b - (b % H);

		int ok = 0;
		for (int i = 0; i < 2 && !ok; i++)
			for (int j = 0; j < 2 && !ok; j++)
			{
				int _A, _B;
				_A = A + i * W;
				_B = B + j * H;

				if (Mp.find( make_pair(_A, _B) ) == Mp.end())
					continue;

				if (isin(a, b, Mp[ make_pair(_A, _B) ]))
					ok = 1;
			}

		NR += ok;
	}
	printf("%d\n", NR);
	return 0;
}