Cod sursa(job #201596)

Utilizator sigridMaria Stanciu sigrid Data 1 august 2008 19:47:18
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<fstream.h>
#define dim 200002

ifstream f("hvrays.in");
ofstream g("hvrays.out");

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

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

punct a[dim],man;


void poz(unsigned long li,unsigned long ls,unsigned long &k)
{
long long 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(unsigned long li, unsigned long ls)
{
if(li<ls)
 {poz(li,ls,k);
  quick(li,k-1);
  quick(k+1,ls);
 }
}



int main()
{
unsigned long i;

f>>t;


while(t)
{
f>>h>>v;

aux=h+v;

for(i=1;i<=h;i++)
 {
  f>>a[i].x>>a[i].y;
  a[i].tip=0;
 }

for(i=h+1;i<=aux;i++)
 {
  f>>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';

t--;
}

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

return 0;

}