Mai intai trebuie sa te autentifici.
Cod sursa(job #201600)
Utilizator | 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;
}