Cod sursa(job #93233)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 18 octombrie 2007 09:07:23
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
/* Ivan Nicolae - HVRAYS */
#include <stdio.h>

#define NMAX 100001
#define _fin  "hvrays.in"
#define _fout "hvrays.out"

int i,j,n,m,H,V,Hx[NMAX],Hy[NMAX],Vx[NMAX],Vy[NMAX],Mark[NMAX];

#define mijloc ((li+ls)>>1)

void Quick_H(int li, int ls)
{
 int i=li, j=ls, x=Hy[mijloc], y;
 while (i<=j)
      {
       while (Hy[i] > x) i++;
       while (Hy[j] < x) j--;
       if (i<=j)
	 {
	  y=Hy[i]; Hy[i]=Hy[j]; Hy[j]=y;
	  y=Vy[i]; Vy[i]=Vy[j]; Vy[j]=y;
	  i++; j--;
	 }
      }
 if (i<ls) Quick_H(i,ls);
 if (li<j) Quick_H(li,j);
}

void Quick_V(int li, int ls)
{
 int i=li, j=ls, x=Vx[mijloc], y;
 while (i<=j)
      {
       while (Vx[i] > x) i++;
       while (Vx[j] < x) j--;
       if (i<=j)
	 {
	  y=Vx[i]; Vx[i]=Vx[j]; Vx[j]=y;
	  y=Vy[i]; Vy[i]=Vy[j]; Vy[j]=y;
	  i++; j--;
	 }
      }
 if (i<ls) Quick_V(i,ls);
 if (li<j) Quick_V(li,j);
}

int main()
{
 freopen(_fin,"r",stdin);
 freopen(_fout,"w",stdout);

 scanf("%d%d",&H,&V);
 for (i=1;i<=H;i++)
    scanf("%d%d",&Hx[i],&Hy[i]);
 for (i=1;i<=V;i++)
    scanf("%d%d",&Vx[i],&Vy[i]);

 int marc=0,rez=0;
 while (marc < H)
      {
       int hu=0;
       for (i=1;i<=H;i++)
	  if (!Mark[i])
	    { hu=i; break; }

       int vu=0;
       for (i=1;i<=V;i++)
	  if (Hx[hu] <= Vx[i] && Hy[hu]<=Vy[i])
	    { vu=i; break; }

       if (vu) rez++;

       for (i=1;i<=H;i++)
	  if (Hx[i] <= Vx[vu] && Hy[i] <= Vy[vu])
	    { Mark[i]=1; marc++; }
      }

 printf("%d",rez);


 fclose(stdin);
 fclose(stdout);
 return 0;
}