Cod sursa(job #92960)

Utilizator VmanDuta Vlad Vman Data 16 octombrie 2007 23:00:04
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
using namespace std;
#include <stdio.h>
#include <algorithm>
#define Max 100001

struct nod { int x,y; };

struct cmp{
bool operator()(const nod &a, const nod &b)const
{
if(a.y>b.y)return 1;
if(a.y==b.y && a.x>b.x)return 1;
return 0;
}
};

int T,V,H,i,nr;
nod h[Max],v[Max];

void solve()
{
int l1=-1,l2=0,max=0;
while (l2<H)
      {
       while (v[l1+1].y>=h[l2].y)
             if (v[++l1].x>max) max=v[l1].x;
       ++nr;
       while ((l2<H)&&(h[l2].x<=max))
             ++l2;
      }
}

int main()
{
      freopen("hvrays.in","r",stdin);
      freopen("hvrays.out","w",stdout);
      scanf("%d",&T);
      while (T>0)
            {
            --T;
            scanf("%d %d",&H,&V);
            for (i=0;i<H;++i)
                scanf("%d %d",&h[i].x,&h[i].y);
            for (i=0;i<V;++i)
                scanf("%d %d",&v[i].x,&v[i].y);
            sort(h,h+H,cmp());
            sort(v,v+V,cmp());
            nr=0;
            solve();
            printf("%d\n",nr);
            }
      fclose(stdout);
      return 0;
}