Cod sursa(job #676812)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 9 februarie 2012 17:01:30
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.h>
#include<algorithm>

#define maxn 100005

using namespace std;

FILE*f=fopen("hvrays.in","r");
FILE*g=fopen("hvrays.out","w");

int h,v;

struct pct{
	int x,y;
}H[maxn],V[maxn];

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

inline void citire () {
	
	fscanf(f,"%d %d",&h,&v);
	
	for ( int i = 1 ; i <= h ; ++i ){
		fscanf(f,"%d %d",&H[i].x,&H[i].y);
	}
	for ( int i = 1 ; i <= v ; ++i ){
		fscanf(f,"%d %d",&V[i].x,&V[i].y);
	}
}

inline int solve () {
	
	sort(H+1,H+h+1,cmp());
	sort(V+1,V+v+1,cmp());
	
	int i,p = v + 1,maxy = -1,res = 0;
	for ( i = h ; i >= 1 ; --i ){
		if ( maxy < H[i].y ){
			while ( p > 0 && V[p-1].x >= H[i].x ){
				--p;
				if ( V[p].y > maxy )	maxy = V[p].y;
			}
			++res;
		}
	}
	
	return res;
}

int main () {
	
	int t;
	
	fscanf(f,"%d",&t);
	for ( int i = 1 ; i <= t ; ++i ){
		citire();
		fprintf(g,"%d\n",solve());
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}