Cod sursa(job #107161)

Utilizator CezarMocanCezar Mocan CezarMocan Data 19 noiembrie 2007 14:02:22
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct nod { int x,y; };

nod v[100010], x[100010], aux;
int i,j,n,m,t,k,nr,ma;

struct cmp{
bool operator()(const nod &a, const nod &b)const
{
if(a.y>b.y)return 1;
if(a.y==b.y && a.x>b.x)return 1;
return 0;
}
};

int main(){
freopen("hvrays.in", "r", stdin);
freopen("hvrays.out", "w", stdout);
scanf("%d",&t);
for (k=1;k<=t;k++)
	{
	scanf("%d%d",&n,&m);
	for (i=0;i<n;i++)
		scanf("%d%d",&v[i].x,&v[i].y);	
	for (i=0;i<m;i++)
		scanf("%d%d",&x[i].x,&x[i].y);	
	sort(v,v+n,cmp());
     sort(x,x+m,cmp());
	nr=0;
	ma=0;
	i=0;j=0;	
	while (i<n)
		{
		j=ma+1;
		while ((x[j].y>=v[i].y) && (j<m))
			{
			if (x[j].x>x[ma].x)
				ma=j;
			j++;
			}
		nr++;
		while ((v[i].x<=x[ma].x)&&(i<n))
			i++;			
		}
	printf("%d \n",nr);			
	}
return 0;	
}