Cod sursa(job #91439)

Utilizator stef2nStefan Istrate stef2n Data 12 octombrie 2007 15:58:04
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define NMAX 100005
struct point {int x,y;};

int NH, NV;
point H[NMAX], V[NMAX];
int cnt;
point maxright, last;

bool cmp(point a, point b)
{
	return a.y>b.y;
}

void solve()
{
	int i, j=0;
	for(i=0; i<NH; ++i)
	{
		while(j<NV && V[j].y>=H[i].y)
		{
			if(maxright.x<V[j].x)
				maxright=V[j];
			++j;
		}
		if(last.x<H[i].x)
		{
			cnt++;
			last=maxright;
		}
	}
}


int main()
{
	freopen("hvrays.in","r",stdin);
	freopen("hvrays.out","w",stdout);
	int t;
	scanf("%d",&t);
	while(t)
	{
		scanf("%d %d",&NH,&NV);
		for(int i=0; i<NH; ++i)
			scanf("%d %d",&H[i].x,&H[i].y);
		for(int i=0; i<NV; ++i)
			scanf("%d %d",&V[i].x,&V[i].y);
		sort(H,H+NH,cmp);
		cnt=0;
		maxright.x=last.x=-1;
		solve();
		printf("%d\n",cnt);
		--t;
	}
	return 0;
}