Cod sursa(job #680774)

Utilizator ChallengeMurtaza Alexandru Challenge Data 15 februarie 2012 21:58:30
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <algorithm>

using namespace std;

const char InFile[]="hvrays.in";
const char OutFile[]="hvrays.out";
const int MaxN=100111;

ifstream fin(InFile);
ofstream fout(OutFile);

struct Point
{
	int x,y;
};

struct Point_cmp
{
	inline bool operator() (const Point &a, const Point &b)
	{
		return a.x<b.x;
	}
};

int T,H,V,sol;
Point Hv[MaxN],Vv[MaxN];

int main()
{
	fin>>T;
	for(register int i=1;i<=T;++i)
	{
		fin>>H>>V;
		for(register int i=1;i<=H;++i)
		{
			fin>>Hv[i].x>>Hv[i].y;
		}
		for(register int i=1;i<=V;++i)
		{
			fin>>Vv[i].x>>Vv[i].y;
		}
		
		sort(Hv+1,Hv+1+H,Point_cmp());
		sort(Vv+1,Vv+1+V,Point_cmp());

		int p=1;
		int curr=-1;
		int xmax=-1;

		sol=0;
		for(register int i=1;i<=H;++i)
		{
			while(p<=V && Hv[i].y<=Vv[p].y)
			{
				xmax=max(xmax,Vv[p].x);
				++p;
			}

			if(curr<Hv[i].x)
			{
				curr=xmax;
				++sol;
			}
		}

		fout<<sol<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}