Cod sursa(job #30240)

Utilizator vmaneavmanea vmanea Data 13 martie 2007 16:17:11
Problema Ograzi Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>

#define nmax 50005
#define mmax 100005

int N, M, W, H;

int i, x, y, suma;

int ogrx[nmax], ogry[nmax];

int oaix[mmax], oaiy[mmax];

int ogx1[nmax], ogy1[nmax];

void msort(int l, int r)
{
	int i, j, k;

	int m = (l + r) >> 1;

	if (l >= r) return;

	msort(l, m);

	msort(m + 1, r);

	for (i = k = l, j = m + 1; i <= m && j <= r; ++k)
		if ((ogrx[i] < ogrx[j]) || (ogrx[i] == ogrx[j] && ogry[i] < ogry[j]))
		{
			ogx1[k] = ogrx[i];
			ogy1[k] = ogry[i];
			++i;
		}
		else
		{
			ogx1[k] = ogrx[j];
			ogy1[k] = ogry[j];
			++j;
		}

	for (; i <= m; ++k)
	{
		ogx1[k] = ogrx[i];
		ogy1[k] = ogry[i];
		++i;
	}

	for (; j <= r; ++k)
	{
		ogx1[k] = ogrx[j];
		ogy1[k] = ogry[j];
		++j;
	}

	for (i = l; i <= r; ++i)
	{
		ogrx[i] = ogx1[i];
		ogry[i] = ogy1[i];
	}
}

int binary(int l, int r)
{
	int m = (l + r) >> 1;

	if (l > r) return 0;


	if (ogrx[m] <= x && x <= ogrx[m] + W && ogry[m] <= y && y <= ogry[m] + H)
		return 1;

	else if (ogrx[m] + W < x || (ogrx[m] <= x && x <= ogrx[m] + W && ogry[m] + H < y))
		return binary(m + 1, r);
	else
		return binary(l, m - 1);
}

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

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

	for (i = 1; i <= N; ++i)
		scanf("%d%d", &ogrx[i], &ogry[i]);

	msort(1, N);

	for (i = 1; i <= M; ++i)
	{
		scanf("%d%d", &x, &y);

		suma += binary(1, N);
	}

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

	return 0;
}