Cod sursa(job #291109)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 29 martie 2009 13:36:13
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
#include<stdio.h>
#include<string.h>
struct pair{long x,y;}x[1500000],y[1500000];
long n,m,i,xc,yc,l,dist,d,p1,p2,s;
char c;
long partit(pair a[ ],long st, long dr)
{long i,j,m;
 pair piv,aa;
 m=(st+dr)/2;
 piv=a[m];
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(a[i].x<piv.x||(a[i].x==piv.x&&a[i].y<piv.y));
   do{--j;} while(a[j].x>piv.x||(a[j].x==piv.x&&a[j].y>piv.y));
   if (i<j)
	 {aa=a[i];a[i]=a[j];a[j]=aa;}
	   else
	 return j;
  }
}
void quicks(pair a[ ],long st,long dr)
{long p;
 if (st<dr)
   {p=partit(a,st,dr);
	quicks(a,st,p);
	quicks(a,p+1,dr);
   }
}
long partit1(pair a[ ],long st, long dr)
{long i,j,m;
 pair piv,aa;
 m=(st+dr)/2;
 piv=a[m];
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(a[i].y<piv.y||(a[i].y==piv.y&&a[i].x<piv.x));
   do{--j;} while(a[j].y>piv.y||(a[j].y==piv.y&&a[j].x>piv.x));
   if (i<j)
	 {aa=a[i];a[i]=a[j];a[j]=aa;}
	   else
	 return j;
  }
}
void quicks1(pair a[ ],long st,long dr)
{long p;
 if (st<dr)
   {p=partit1(a,st,dr);
	quicks1(a,st,p);
	quicks1(a,p+1,dr);
   }
}
long cby(pair a[],long st,long dr,long x,long y)
{long m;
 while(st<=dr)
  {m=(st+dr)/2;
   if(a[m].x==x)
     {if(a[m].y==y)return m;
        else
      if(a[m].y<y)st=m+1;
        else
      if(a[m].y>y)dr=m-1;}
     else
   if(a[m].x<x)st=m+1;
     else
   if(a[m].x>x)dr=m-1;}
 return st;
}
long cbx(pair a[],long st,long dr,long x,long y)
{long m;
 while(st<=dr)
  {m=(st+dr)/2;
   if(a[m].y==y)
     {if(a[m].x==x)return m;
        else
      if(a[m].x<x)st=m+1;
        else
      if(a[m].x>x)dr=m-1;}
     else
   if(a[m].y<y)st=m+1;
     else
   if(a[m].y>y)dr=m-1;}
 return st;
}
int main()
{
 freopen("zc.in","r",stdin);
 freopen("zc.out","w",stdout);
 scanf("%ld%ld",&n,&m);
 for(i=1;i<=n;++i)
    {scanf("%ld%ld\n",&yc,&xc);
     if(xc!=0||yc!=0)x[++l].x=xc,x[l].y=yc;
     if(xc+1!=0||yc!=0)x[++l].x=xc+1,x[l].y=yc;
     if(xc-1!=0||yc!=0)x[++l].x=xc-1,x[l].y=yc;
     if(xc!=0||yc+1!=0)x[++l].x=xc,x[l].y=yc+1;
     if(xc!=0||yc-1!=0)x[++l].x=xc,x[l].y=yc-1;
     if(xc+1!=0||yc+1!=0)x[++l].x=xc+1,x[l].y=yc+1;
     if(xc-1!=0||yc-1!=0)x[++l].x=xc-1,x[l].y=yc-1;
     if(xc-1!=0||yc+1!=0)x[++l].x=xc-1,x[l].y=yc+1;
     if(xc+1!=0||yc-1!=0)x[++l].x=xc+1,x[l].y=yc-1;
     if(xc+2!=0||yc!=0)x[++l].x=xc+2,x[l].y=yc;
     if(xc-2!=0||yc!=0)x[++l].x=xc-2,x[l].y=yc;
     if(xc!=0||yc+2!=0)x[++l].x=xc,x[l].y=yc+2;
     if(xc!=0||yc-2!=0)x[++l].x=xc,x[l].y=yc-2;}
 quicks(x,1,l);
 dist=0;
 for(i=1;i<=l;++i)
    {x[i]=x[i+dist];                                    
     while(x[i].x==x[i-1].x&&x[i].y==x[i-1].y&&i<=l-dist){++dist,x[i]=x[i+dist];}};
 l-=dist;
 memcpy(y,x,sizeof(x));
 quicks1(y,1,l);
 xc=0;
 yc=0;
 for(i=1;i<=m;++i)
    {scanf("%c %ld\n",&c,&d);
     if(c=='N'||c=='S')
       {p1=cbx(y,1,l,xc,yc);
        while(y[p1].x<xc||y[p1].y<yc||p1<1)++p1;
        if(c=='S')d*=(-1);
        xc+=d;
        p2=cbx(y,1,l,xc,yc);
        while(y[p2].x>xc||y[p2].y>yc||p2>l)--p2;
        if(p2>=p1)s+=(p2-p1+1);}
       else
       {p1=cby(x,1,l,xc,yc);
        while(x[p1].y<yc||x[p1].x<xc||p1<1)++p1;
        if(c=='V')d*=(-1);
        yc+=d;
        p2=cby(x,1,l,xc,yc);
        while(x[p2].y>yc||x[p2].x>xc||p2>l)--p2;
        if(p2>=p1)s+=(p2-p1+1);}}
 printf("%ld\n",s);
 return 0;
}