Cod sursa(job #90409)

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

#include <algorithm>
#include <vector>

using namespace std;

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

int i, H, V, x, y, nv, xv, xc;
vector<pair<int, pair<int, int> > > v;

#define X(i) (v[i].second.second)
#define Y(i) (v[i].first)
#define T(i) (v[i].second.first)

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);

		v.clear();

		for (i = 1; i <= H; i++)
		{
			scanf("%d %d", &x, &y);
			v.push_back(make_pair(y, make_pair(HORIZ, x)));
		}

		for (i = 1; i <= V; i++)
		{
			scanf("%d %d", &x, &y);
			v.push_back(make_pair(y, make_pair(VERT, x)));
		}

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

		xc = xv =-INF;
		nv = 0;

		fprintf(stderr, "### Test %d\n", te);
		/*
		for (i = H + V - 1; i >= 0; i--)
			fprintf(stderr, "i=%d: y=%d, x=%d, t=%d\n", H + V - i, Y(i), X(i), T(i));		
		*/

		for (i = H + V - 1; i >= 0; i--)
			if (T(i) == VERT)
			{
				if (X(i) > xv)
					xv = X(i);
			}
			else
			{
				if (xv < X(i))
				{
					nv = -1;
					break;
				}

				if (X(i) > xc)
				{
					nv++;
					xc = xv;
				}
			}

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

	return 0;
}