Cod sursa(job #485949)

Utilizator bora_marianBora marian bora_marian Data 19 septembrie 2010 23:25:57
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<fstream>
using namespace std;
struct point{
   int x,y;};
point v[100010],h[100010];
int H,V,nrsol,t,gata,valmax;
inline bool cmp(const point& a, const point& b);
void solve();
int maxim(int a,int b);
int main()
{
	freopen("hvrays.in", "r", stdin);
	freopen("hvrays.out", "w", stdout);
	int t, i, idv, coltx;
	int cs; // cardinal submultime
	scanf("%d", &t);
	while(t--)
	{
		//citire
		scanf("%d%d", &H, &V);
		for(i =1; i<=H; ++i) 
		{	
			scanf("%d%d", &h[i].x, &h[i].y);
			if(h[i].x>valmax)
				valmax=h[i].x;
		}
		for(i=1; i<=V; ++i) 
			scanf("%d%d", &v[i].x, &v[i].y);

		nrsol=0;
		solve();
		printf("%d\n", nrsol);
	}
	return 0;
}
void solve()
{
	int i,j;
	sort(h+1,h+H+1,cmp);
	sort(v+1,v+V+1,cmp);
	int dep=-1,cam=1;
	for(i=1;i<=H && gata==0;i++)
	{	
		if(h[i].x>dep)
		{
			nrsol++;
			int pp=0;
			for(j=cam;j<=V && pp==0;j++)
			{	
				if(v[j].y>=h[i].y)
					dep=maxim(dep,v[j].x),cam++;
				else
					pp=1;
			}
		}
	}
}
int maxim(int a,int b)
{
	if(a>b)
		return a;
	else
		return b;
}
inline bool cmp(const point& a, const point& b)
{
	if(a.y == b.y)
		return a.x > b.x;
	return a.y > b.y;
}