Cod sursa(job #486167)

Utilizator loginLogin Iustin Anca login Data 20 septembrie 2010 18:02:44
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 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.x==b.x)return a.y<b.y;
		return a.x<b.x;
	}
}H[DIM], V[DIM];
int t, h, v, u[DIM];

int solve ()
{
	for(int i=1;i<=h;++i)u[i]=0;
	int sol=0, x=-1, y=-1;
	sort (H+1,H+h+1);
	sort (V+1,V+v+1);
	for(int i=1;i<=v;)
	{
		++sol;
		for(int j=1;j<=h;++j)
			if (H[j].x<=V[i].x && H[j].y<=V[i].y && !u[j])
			{
				if (H[j].x>x)x=H[j].x;
				if (H[j].y>y)y=H[j].y;
				u[j]=1;
			}
		++i;
		while (V[i].x>=x && V[i].y>=y)
			++i;
	}
	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;
}