Cod sursa(job #66252)

Utilizator peanutzAndrei Homorodean peanutz Data 17 iunie 2007 08:57:17
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.24 kb
#include <stdio.h>
#include <string.h>
#define cmax 1300002
#define logmax 27

long n,m,i,j,d,nr,nr2,xx,yy,
     x[cmax],y[cmax],vx[cmax],vy[cmax];
char c;

void qsort1(long l, long r)
{
 long i,j,m,aux;
 i=l;
 j=r;
 m=vx[(l+r)/2];
 do
	{
	while (((x[vx[i]]<x[m])||((x[vx[i]]==x[m])&&(y[vx[i]]<y[m])))&&(i<r)) ++i;
	while (((x[m]<x[vx[j]])||((x[m]==x[vx[j]])&&(y[m]<y[vx[j]])))&&(j>1)) --j;
	if (i<=j)
		{
		aux=vx[i];vx[i]=vx[j];vx[j]=aux;
		++i;
		--j;
		}
	}
 while (i<=j);
 if (l<j) qsort1(l,j);
 if (i<r) qsort1(i,r);
}

void qsort2(long l, long r)
{
 long i,j,m,aux;
 i=l;
 j=r;
 m=vy[(l+r)/2];
 do
	{
	while (((y[vy[i]]<y[m])||((y[vy[i]]==y[m])&&(x[vy[i]]<x[m])))&&(i<r)) ++i;
	while (((y[m]<y[vy[j]])||((y[m]==y[vy[j]])&&(x[m]<x[vy[j]])))&&(j>1)) --j;
	if (i<=j)
		{
		aux=vy[i];vy[i]=vy[j];vy[j]=aux;
		++i;
		--j;
		}
	}
 while (i<=j);
 if (l<j) qsort2(l,j);
 if (i<r) qsort2(i,r);
}

void add(long xx,long yy)
{
          if ((xx==0)&&(yy==0)) return;
          ++nr;
          vx[nr]=nr;
          x[nr]=xx;
          y[nr]=yy;
}

void cautax(long xi,long yi,long yf)
{
long p=0,st,dr,k=1;
char i;
for (i=logmax;i>=0;--i)
    if (((p+(k<<i))<=nr2)&&(x[vx[p+(k<<i)]]<xi))
	{
	p+=(k<<i);
	}
p+=1;
if (x[vx[p]]!=xi) return;
st=p;
while ((x[vx[st]]==xi)&&(y[vx[st]]<yi)&&(st<=nr2)) ++st;
dr=st;
while ((x[vx[dr]]==xi)&&(y[vx[dr]]<=yf)&&(dr<=nr2)) ++dr;
nr+=dr-st;
}

void cautay(long xi,long yi,long xf)
{
long p=0,st,dr,k=1;
char i;
for (i=logmax;i>=0;--i)
    if (((p+(k<<i))<=nr2)&&(y[vy[p+(k<<i)]]<yi))
	{
	p+=(k<<i);
	}
p+=1;
if (y[vy[p]]!=yi) return;
st=p;
while ((y[vy[st]]==yi)&&(x[vy[st]]<xi)&&(st<=nr2)) ++st;
dr=st;
while ((y[vy[dr]]==yi)&&(x[vy[dr]]<=xf)&&(dr<=nr2)) ++dr;
nr+=dr-st;
}

int main()
{
      freopen("zc.in","r",stdin);
      scanf("%ld %ld\n",&n,&m);
      for (i=0;i<n;++i)
          {
	  scanf("%ld %ld\n",&yy,&xx);
          add(xx-2,yy);
          add(xx-1,yy-1);
          add(xx-1,yy);
          add(xx-1,yy+1);
          add(xx,yy-2);
          add(xx,yy-1);
          add(xx,yy);
          add(xx,yy+1);
          add(xx,yy+2);
          add(xx+1,yy-1);
          add(xx+1,yy);
          add(xx+1,yy+1);
          add(xx+2,yy);
          }
      qsort1(1,nr);
      //elimin dublurile
      nr2=1;
      for (i=1;i<=nr-1;++i)
          {
          if ((x[vx[i]]!=x[vx[i+1]])||(y[vx[i]]!=y[vx[i+1]]))
             {
	          nr2++;
              vx[nr2]=vx[i+1];
             }
          }
      //sortez dupa y
      memcpy(vy,vx,sizeof(vx));
      qsort2(1,nr2);
      xx=0;
      yy=0;
      nr=0;
      for (i=0;i<m;++i)
          {
           scanf("%c %ld\n",&c,&d);
           --d;
	   if (c=='N')
	      {
          ++xx;
	      cautay(xx,yy,xx+d);
	      xx+=d;
	      }
	      else
	   if (c=='S')
	      {
          --xx;
	      cautay(xx-d,yy,xx);
	      xx-=d;
	      }
	      else
	   if (c=='E')
	      {
          ++yy;
	      cautax(xx,yy,yy+d);
	      yy+=d;
	      }
	      else
	      {
          --yy;
	      cautax(xx,yy-d,yy);
	      yy-=d;
	      }
	  }
      fclose(stdin);
      freopen("zc.out","w",stdout);
      printf("%ld",nr);
      fclose(stdout);
      return 0;
}