Cod sursa(job #82712)

Utilizator flionIonescu Ionut Florin flion Data 8 septembrie 2007 15:36:01
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <stdio.h>

#define nmax 50005

#define mmax 100005

#define lmax 10005

#define lgmax 15

int segment[lgmax*lmax];

int x[nmax + nmax + mmax], x2[nmax + mmax + nmax];

int y[nmax + nmax + mmax], y2[nmax + mmax + nmax];

int vx[nmax + nmax + mmax], vx2[nmax + mmax + nmax];

int vy[nmax + nmax + mmax], vy2[nmax + mmax + nmax];

int N, M, W, H, NNM, i, oi;



void insert(int nod, int st, int dr, int a, int b)
{
	// inserez intervalul [a, b] in [st, dr];
	if (a <= st && dr <= b)
	{
		segment[nod]=1;
	}
	else
	{
		int m = (st + dr) >> 1;

		if (a <= m)
		{
			insert(nod << 1, st, m, a, b);
		}

		if (m < b)
		{
			insert(nod << 1|1, m+1, dr, a, b);
		}

		if (segment[nod<<1] && segment[nod<<1|1])
			segment[nod] = 1;
	}
}

void xtract(int nod, int st, int dr, int a, int b)
{
	// sterg intervalul [a, b] in [st, dr];
	if (a <= st && dr <= b)
	{
		segment[nod] = 0;
	}
	else
	{
		int m = (st + dr) >> 1;

		if (a <= m)
		{
			xtract(nod << 1, st, m, a, b);
		}

		if (m < b)
		{
			xtract(nod << 1|1, m+1, dr, a, b);
		}

		segment[nod] = 0;
	}
}

int query(int nod, int st, int dr, int x)
{
	if (segment[nod] == 1)
		return segment[nod];

	if (st == dr && st == x)
	{
		return (segment[nod] > 0);
	}
	else
	{
		int m = (st + dr) >> 1;

		if (x <= m)
		{
			return query(nod << 1, st, m, x);
		}
		else
		{
			return query(nod<<1|1, m+1, dr, x);
		}
	}
}

void msort(int l, int r)
{
	if (l >= r) return;

	int m = (l + r) >> 1, i, j, k;

	msort(l, m);

	msort(m+1, r);

	for (i = l, j = m+1, k = l; i <= m && j <= r; k++)
	{
		if (x[i] < x[j] || (x[i] == x[j] && (y[i] <= y[j] || vx[i] < vx[j]) ))
		{
			x2[k] = x[i];
			y2[k] = y[i];
			vx2[k] = vx[i];
			vy2[k] = vy[i];
			i++;
		}
		else
		{
			x2[k] = x[j];
			y2[k] = y[j];
			vx2[k] = vx[j];
			vy2[k] = vy[j];
			j++;
		}
	}
	for (; i <= m; i++, k++)
	{
		x2[k] = x[i];
		y2[k] = y[i];
		vx2[k] = vx[i];
		vy2[k] = vy[i];
	}
	for (; j <= r; j++, k++)
	{
		x2[k] = x[j];
		y2[k] = y[j];
		vx2[k] = vx[j];
		vy2[k] = vy[j];
	}
	for (k = l; k <= r; k++)
	{
		x[k] = x2[k];
		y[k] = y2[k];
		vx[k] = vx2[k];
		vy[k] = vy2[k];
	}
}

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

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

	// citesc dreptunghiurile
	for (i = 1; i <= N; i++)
	{
		scanf("%d%d", &x[i], &y[i]);
		vx[i] = vy[i] = i;
		vx[i+N+M] = vy[i+N+M] = i+N+M;

		x[i+N+M] = x[i] + W;
		y[i+N+M] = y[i] + H;
	}

	// citesc oile
	for (i = 1; i <= M; i++)
	{
		scanf("%d%d", &x[i+N], &y[i+N]);
		vx[i+N] = vy[i+N] = i+N;
	}

	// sortez dupa x si dupa y punctele si oile,
	// in aceasta ordine la egalitate:
	msort(1, N+N+M);

	// parcurg punctele
	for (i = 1, NNM = N + N + M; i <= NNM; i++)
	{
		if (vx[i] <= N) // punct de intrare
		{
			insert(1, 1, lgmax, y[i], y[i]+H);
		}
		else if (vx[i] <= N + M) // punct de oaie
		{
			oi += query(1, 1, lgmax, y[i]);
		}
		else
		{
			xtract(1, 1, lgmax, y[i]-H, y[i]);
		}
	}

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

	return 0;
}