Pagini recente » Cod sursa (job #690316) | Cod sursa (job #298287) | Cod sursa (job #3240515) | Cod sursa (job #429393) | Cod sursa (job #495498)
Cod sursa(job #495498)
#include <stdio.h>
#include <deque>
#include <algorithm>
#define Nmax 100000+2
using namespace std;
deque< int > Q;
struct punct{ int x,y; } H[Nmax],V[Nmax];
int Nh,Nv,T;
inline int Maxim(int x,int y){ return x>y ? x:y; }
inline int cmp(punct a, punct b){
return a.x<b.x || (a.x==b.x && a.y<b.y);
}
int main(){
int i,j,nr,tall;
freopen("hvrays.in","r",stdin);
freopen("hvrays.out","w",stdout);
for( scanf("%d",&T); T; --T){
scanf("%d%d",&Nh,&Nv);
for(i=1;i<=Nh;++i) scanf("%d%d",&H[i].x,&H[i].y);
for(i=1;i<=Nv;++i) scanf("%d%d",&V[i].x,&V[i].y);
sort(H+1,H+Nh+1,cmp);
sort(V+1,V+Nv+1,cmp);
while( !Q.empty() ) Q.pop_back();
j=1;
for(i=1;i<=Nv;++i){
nr=0; tall=0;
while( j<=Nh && H[j].x<=V[i].x && H[j].y<=V[i].y ){
tall=Maxim(tall,H[j].y);
++nr,++j;
}
if( Q.empty() ){
if(nr) Q.push_back(tall);
}
else
if( Q.back() <= V[i].y || nr ){
while( !Q.empty() && Q.back() <= V[i].y ){
tall=Maxim(tall,Q.back());
Q.pop_back();
}
Q.push_back(tall);
}
}
printf("%d\n",Q.size());
}
fclose(stdin); fclose(stdout);
return 0;
}