Cod sursa(job #201600)

Utilizator sigridMaria Stanciu sigrid Data 1 august 2008 20:01:03
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>
#define dim 200002

freopen("hvrays.in","r",stdin);
freopen("hvrays.out","w",stdout);

long int h,v,cont,aux,max,pmax,k;
int t;

struct punct
{
long int x;
long int y;
int tip;
};

punct a[dim],man;


void poz(long int li, long int ls, long int &k)
{
long int i=li,j=ls,i1=0,j1=-1,c;

while(i<j)
 {
  if(a[i].x>a[j].x)
   {
    man=a[j];
    a[j]=a[i];
    a[i]=man;

    c=i1;
    i1=-j1;
    j1=-c;
   }

  i+=i1;
  j+=j1;
 }

k=i;
}

void quick(long int li, long int ls)
{
if(li<ls)
 {poz(li,ls,k);
  quick(li,k-1);
  quick(k+1,ls);
 }
}



int main()
{
long int i;

//f>>t;
scanf("%ld",&t);

while(t)
{
//f>>h>>v;
scanf("%ld %ld",&h,&v);

aux=h+v;

for(i=1;i<=h;i++)
 {
  //f>>a[i].x>>a[i].y;
  scanf("%ld %ld",&a[i].x,&a[i].y);
  a[i].tip=0;
 }

for(i=h+1;i<=aux;i++)
 {
  //f>>a[i].x>>a[i].y;
  scanf("%ld %ld",&a[i].x,&a[i].y);
  a[i].tip=1;
 }




//sort();
quick(1,aux);

for(i=aux;i>=1;i--)
 {
  if( a[i].tip==1 && a[i].y>pmax )
    pmax=a[i].y;
   else if( !a[i].tip )
       {
	if( a[i].y>max )
	   {
	    max=pmax;
	    cont++;
	   }
       }

 }

//g<<cont<<'\n';
printf("%ld\n",cont);

t--;
}

//f.close();
//g.close();

return 0;

}