Cod sursa(job #486560)

Utilizator loginLogin Iustin Anca login Data 21 septembrie 2010 23:08:34
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
# include <fstream>
# include <algorithm>
# define DIM 100003
using namespace std;
struct nod{
	int x, y;
	friend bool operator < (const nod &a, const nod &b){
		if (a.y==b.y)return a.x>b.x;
		return a.y>b.y;
	}
}H[DIM], V[DIM];
int t, h, v, u[DIM];

int solve ()
{
	int sol=0, i, j, x=0, st=1;
	sort (H+1,H+h+1);
	sort (V+1,V+v+1);
	for(i=1;i<=h;++i)
		if (H[i].x>x)
		{
			++sol;
			for(j=st;j<=v && V[j].y>=H[i].y;++j)
				if (V[j].x<H[i].x)++st;
				else if (V[j].x>x)x=V[j].x, ++st;
		}
	return sol;
}

int main ()
{
	ifstream fin ("hvrays.in");
	ofstream fout ("hvrays.out");
	fin>>t;
	for (;t--;)
	{
		fin>>h>>v;
		for(int i=1;i<=h;++i)
			fin>>H[i].x>>H[i].y;
		for(int i=1;i<=v;++i)
			fin>>V[i].x>>V[i].y;
		fout<<solve()<<endl;
	}
	return 0;
}