Cod sursa(job #195004)

Utilizator andrei.12Andrei Parvu andrei.12 Data 15 iunie 2008 20:52:34
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<algorithm>

using namespace std;

#define x first
#define y second
#define lg 100005

int teste, i, h, v, nr, j, mx, p;
typedef pair<int, int> ii;
ii vh[lg], vv[lg];

inline int cmp(ii a, ii b){
	if (a.x != b.x)
		return a.x > b.x;
	return a.y < b.y;
}

int main()
{
	freopen("hvrays.in", "rt", stdin);
	freopen("hvrays.out", "wt", stdout);

	scanf("%d", &teste);
	while (teste --){
		scanf("%d%d", &h, &v);
		for (i = 1; i <= h; i ++)
			scanf("%d%d", &vh[i].x, &vh[i].y);
		for (i = 1; i <= v; i ++)
			scanf("%d%d", &vv[i].x, &vv[i].y);

		sort(vh+1, vh+h+1, cmp);
		sort(vv+1, vv+v+1, cmp);
		
		nr = 0, mx = 0, p = 1;
		for (i = 1; i <= h; i ++)
			if (i == 1 || mx < vh[i].y){
				nr ++;
				for (j = p; vv[j].x >= vh[i].x && j <= v; j ++)
					mx = max(mx, vv[j].y);
				p = j;
				//printf("%d\n", mx);
			}

		printf("%d\n", nr);
	}

	return 0;
}