Cod sursa(job #27371)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 6 martie 2007 13:05:09
Problema Ograzi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <vector>

#include <cstdlib>
#include <ctime>

using namespace std;

#define MAXN 50005
#define MAXP 1000007

int x[MAXN], y[MAXN];
int r1, r2;

//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;
vector<int> Mp[MAXP];

inline int hashPoint( pair<int, int> P )
{
	return (P.first * r1 + P.second * r2) % MAXP;
}

inline 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()
{
	srand( time(0) );
	r1 = rand() % 2007;
	r2 = rand() % 2007;

	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[ hashPoint( getPoint(i) ) ].push_back(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';

		if (a % W)
			A = a - (a % W);
		else
			A = a - W;
		if (b % H)
			B = b - (b % H);
		else
			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;

				int pct = hashPoint( make_pair(_A, _B) );

				for (size_t k = 0; k < Mp[ pct ].size() && !ok; k++)
					if (isin(a, b, Mp[ pct ][k]))
						ok = 1;
			}

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