Cod sursa(job #483687)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 9 septembrie 2010 18:43:56
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>

#include <algorithm>

using namespace std;

struct point
{
	int x, y;
};

int n, m;
point o[100002], v[100002];

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

int main ()
{
	freopen ("hvrays.in", "r", stdin);
	freopen ("hvrays.out", "w", stdout);
	
	int t, i, j, x, nr;
	
	scanf ("%d", &t);
	while (t --)
	{
		nr = 0;
		scanf ("%d %d", &n, &m);
		
		for (i = 1; i <= n; i ++)
			scanf ("%d %d", &o[i].x, &o[i].y);
		for (i = 1; i <= m; i ++)
			scanf ("%d %d", &v[i].x, &v[i].y);
		
		sort (o + 1, o + n + 1, cmp);
		sort (v + 1, v + m + 1, cmp);
		
		i = j = 1;
		while (i <= n)
		{
			x = v[j].x;
			while (j <= m && v[j].y >= o[i].y)
			{
				if (v[j].x > x)
					x = v[j].x;
				j ++;
			}
			while (i <= n && x >= o[i].x)
				i ++;
			nr ++;
		}
		
		printf ("%d\n", nr);
	}
	return 0;
}