Cod sursa(job #90412)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 9 octombrie 2007 13:27:15
Problema Hvrays Scor Ascuns
Compilator cpp Status done
Runda Marime 1.42 kb
#include <stdio.h>

#include <algorithm>
#include <vector>

using namespace std;

#define HORIZ 0
#define VERT 1
#define INF 666666666
#define NMAX 100100

int i, j, k, H, Hnew, V, nv, ymax, xmax;
int xh[NMAX], yh[NMAX], xv[NMAX], yv[NMAX];

int main()
{
	int te, T;

	freopen("hvrays.in", "r", stdin);
	freopen("hvrays.out", "w", stdout);

	scanf("%d", &T);

	for (te = 1; te <= T; te++)
	{
		scanf("%d %d", &H, &V);

		for (i = 1; i <= H; i++)
		{
			scanf("%d %d", &xh[i], &yh[i]);

			if (xh[i] < 0 || xh[i] > 50000000 || yh[i] < 0 || yh[i] > 50000000)
				fprintf(stderr, "bug?\n");
		}

		for (i = 1; i <= V; i++)
		{
			scanf("%d %d", &xv[i], &yv[i]);

			if (xv[i] < 0 || xv[i] > 50000000 || yv[i] < 0 || yv[i] > 50000000)
				fprintf(stderr, "bug?\n");
		}

		nv = 0;

		while (H > 0 && V > 0)
		{
			ymax = -1;

			for (i = 1; i <= H; i++)
				if (yh[i] > ymax)
					ymax = yh[i];

			xmax = -1;

			for (i = 1; i <= V; i++)
				if (yv[i] >= ymax && xv[i] >= xmax)
					xmax = xv[i],
					k = i;

			if (xmax < 0)
				break;

			nv++;

			Hnew = 0;

			for (j = 1; j <= H; j++)
				if (!(xh[j] <= xv[k] && yh[j] <= yv[k]))
				{
					Hnew++;
					xh[Hnew] = xh[j];
					yh[Hnew] = yh[j];
				}

			H = Hnew;

			for (i = k + 1; i <= V; i++)
			{
				xv[i - 1] = xv[i];
				yv[i - 1] = yv[i];
			}

			V--;
		}

		if (H > 0)
			nv = -1;

		printf("%d\n", nv);
		fprintf(stderr, "-> Sol=%d [Hleft=%d; Vleft=%d]\n", nv, H, V);
	}

	return 0;
}