Cod sursa(job #26029)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 5 martie 2007 01:23:58
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <stdio.h>
#include <string.h>
#include <stdio.h>
//#include <time.h>

#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 100100
#define LMAX 1000
#define BUFSIZE 2097152

typedef pair< pair<int, int>, int > punct;

vector<punct> vp;

#define X(u) (vp[u].first.first)
#define Y(u) (vp[u].first.second)
#define D(u) (vp[u].second)

char buf[BUFSIZE];
char s[LMAX + 1];
int xd[NMAX], yd[NMAX];
int i, j, k, iw, jh, N, M, W, H, cnt, xp, yp;

int inline inside(int x, int y) // the point's coordinates are (xp, yp)
{
	int li = 0, ls = vp.size() - 1, mid, xx, yy;

	while (li <= ls)
	{
		mid = (li + ls) >> 1;

		xx = X(mid);
		yy = Y(mid);

		if (xx < x)
			li = mid + 1;
		else
		if (xx > x)
			ls = mid - 1;
		else // xx == x
		{
			if (yy < y)
				li = mid + 1;
			else
			if (yy > y)
				ls = mid - 1;
			else // xx == x && yy == y
				break;
		}
	}

	if (li <= ls)
	{
		xx = D(mid);

		if (xp >= xd[xx] && xp <= xd[xx] + W && yp >= yd[xx] && yp <= yd[xx] + H)
			return 1;
		else
			return 0;
	}
	else
		return 0;
}

int main()
{
	freopen("ograzi.in", "r", stdin);
	setvbuf(stdin, buf, _IOFBF, BUFSIZE);

	vp.clear();
	s[0] = 0;
	
	fgets(s, LMAX, stdin);

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

	for (k = 1; k <= N; k++)
	{
		s[0] = 0;
		fgets(s, LMAX, stdin);
		sscanf(s, "%d%d", &i, &j);

		xd[k] = i;
		yd[k] = j;

		iw = (i / W) * W;
		jh = (j / H) * H;

		if (iw >= i && iw <= i + W && jh >= j && jh <= j + H)
			vp.push_back(make_pair(make_pair(iw, jh), k));

		if (iw + W >= i && iw + W <= i + W && jh >= j && jh <= j + H)
			vp.push_back(make_pair(make_pair(iw + W, jh), k));

		if (iw >= i && iw <= i + W && jh + H >= j && jh + H <= j + H)
			vp.push_back(make_pair(make_pair(iw, jh + H), k));

		if (iw + W >= i && iw + W <= i + W && jh + H >= j && jh + H <= j + H)
			vp.push_back(make_pair(make_pair(iw + W, jh + H), k));
	}

	sort(vp.begin(), vp.end());

	cnt = 0;

	for (k = 1; k <= M; k++)
	{
		s[0] = 0;
		fgets(s, LMAX, stdin);

		sscanf(s, "%d%d", &xp, &yp);

		iw = (xp / W) * W;
		jh = (yp / H) * H;

		if (inside(iw, jh))
			cnt++;
		else
		if (inside(iw + W, jh))
			cnt++;
		else
		if (inside(iw, jh + H))
			cnt++;
		else
		if (inside(iw + W, jh + H))
			cnt++;
	}

	//fprintf(stderr, "%d\n", clock());


	freopen("ograzi.out", "w", stdout);

	printf("%d\n", cnt);

	return 0;
}