Cod sursa(job #27312)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 6 martie 2007 12:27:26
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 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);
}

char tmp[16], *p;

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++)
	{
		fgets(tmp, 16, stdin);
		for (p = tmp, x[i] = 0; '0' <= *p && *p <= '9'; p++)
			x[i] = x[i] * 10 + *p - '0';
		for (p++, y[i] = 0; '0' <= *p && *p <= '9'; p++)
			y[i] = y[i] * 10 + *p - '0';
		Mp[ getPoint(i) ] = i;
	}

	int NR = 0;

	for (; M; M--)
	{
		int a, b, A, B;
		fgets(tmp, 16, stdin);
		for (p = tmp, a = 0; '0' <= *p && *p <= '9'; p++)
			a = a * 10 + *p - '0';
		for (p++, b = 0; '0' <= *p && *p <= '9'; p++)
			b = b * 10 + *p - '0';

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

//		printf("%d %d\n", a, b);

		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;

//				printf("\t%d %d\n", _A, _B);
				if (Mp.find( make_pair(_A, _B) ) == Mp.end())
					continue;
//				printf("\tfok\n");

				if (isin(a, b, Mp[ make_pair(_A, _B) ]))
//				{
					ok = 1;
//					printf("\tsok\n");
//				}
			}

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