Cod sursa(job #68964)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 30 iunie 2007 14:45:07
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 kb
#include<stdio.h>

typedef struct
{
  long x,y;
} coord;

coord a;

coord vx[1000000],vy[1000000];

long n, m, nr;

void bubley(coord x[])
{
  long i, j, ok=1;
  coord aux;
  while (ok)
    {
      ok=0;
      for (i=1; i<nr; i++)
	if (x[i].y>x[i+1].y || (x[i].y==x[i+1].y && x[i].x>x[i+1].x))
	  {
	    aux=x[i];
	    x[i]=x[i+1];
	    x[i+1]=aux;
	    ok=1;
	  }
    }
}

void bublex(coord x[])
{
  long i, j, ok=1;
  coord aux;
  while (ok)
    {
      ok=0;
      for (i=1; i<nr; i++)
	if (x[i].x>x[i+1].x || (x[i].x==x[i+1].x && x[i].y>x[i+1].y))
	  {
	    aux=x[i];
	    x[i]=x[i+1];
	    x[i+1]=aux;
	    ok=1;
	  }
    }
}

int cautarex(coord x)
{
  long i, j, m;
  i=1; j=nr;
  m=(i+j)/2;
  while (i<=j)
    {
      if (vx[m].x==x.x && vx[m].y==x.y) return 1;
      else if (vx[m].x==x.x) if(vx[m].y>x.y) {j=m-1; m=(i+j)/2;}
				    else {i=m+1; m=(i+j)/2;}
	    else if (vx[m].x>x.x) {j=m-1; m=(i+j)/2;}
			else {i=m+1; m=(i+j)/2;}
    }
  return 0;
}

int cautarey(coord x)
{
  long i, j, m;
  i=1; j=nr;
  m=(i+j)/2;
  while (i<=j)
    {
      if (vy[m].x==x.x && vy[m].y==x.y) return 1;
      else if (vy[m].y==x.y) if(vy[m].x>x.x) {j=m-1; m=(i+j)/2;}
				    else {i=m+1; m=(i+j)/2;}
	    else if (vy[m].y>x.y) {j=m-1; m=(i+j)/2;}
			else {i=m+1; m=(i+j)/2;}
    }
  return 0;
}


int main()
{
  freopen("zc.in","r",stdin);
  freopen("zc.out","w",stdout);

  scanf("%ld %ld",&n,&m);
  long i, j, d;
  for (i=1; i<=n; i++)
    {
      nr++;
      scanf("%ld %ld",&vx[nr].x,&vx[nr].y);
      if (vx[nr].x!=0 || vx[nr].y!=0) {
      vy[nr].x=vx[nr].x;
      vy[nr].y=vx[nr].y;} else nr--;
      d=nr;
	if (vx[nr].x-2!=0 || vx[nr].y!=0){
      nr++;
      vx[nr].x=vy[nr].x=vx[d].x-2;
      vy[nr].y=vx[nr].y=vx[d].y;}
        
	if (vx[nr].x-1!=0 || vx[nr].y!=0){
      nr++;
      vx[nr].x=vy[nr].x=vx[d].x-1;
      vy[nr].y=vx[nr].y=vx[d].y;}

	if (vx[nr].x+1!=0 || vx[nr].y!=0){
      nr++;
      vx[nr].x=vy[nr].x=vx[d].x+1;
      vy[nr].y=vx[nr].y=vx[d].y;}

	if (vx[nr].x+2!=0 || vx[nr].y!=0){
      nr++;
      vx[nr].x=vy[nr].x=vx[d].x+2;
      vy[nr].y=vx[nr].y=vx[d].y;}

	if (vx[nr].x!=0 || vx[nr].y-2!=0){
      nr++;
      vx[nr].x=vy[nr].x=vx[d].x;
      vy[nr].y=vx[nr].y=vx[d].y-2;}

	if (vx[nr].x!=0 || vx[nr].y-1!=0){
      nr++;
      vx[nr].x=vy[nr].x=vx[d].x;
      vy[nr].y=vx[nr].y=vx[d].y-1;}

	if (vx[nr].x!=0 || vx[nr].y+1!=0){
      nr++;
      vx[nr].x=vy[nr].x=vx[d].x;
      vy[nr].y=vx[nr].y=vx[d].y+1;}

	if (vx[nr].x!=0 || vx[nr].y+2!=0){
      nr++;
      vx[nr].x=vy[nr].x=vx[d].x;
      vy[nr].y=vx[nr].y=vx[d].y+2;}
    }
  bublex(vx);
  bubley(vy);

  

  a.x=a.y=0;
  long contor=0;
  for (i=1; i<=m; i++)
    {
      char c;
      long l, x;
      scanf("%c",&c);
      while (c=='\n') {scanf("%c",&c);}
      scanf("%ld",&l);

      switch (c)
	{
	  case 'N' :{x=a.y+l;while (a.y<=x)
			{ a.y++; if (cautarey(a) && cautarex(a)) contor++;}
		     break;
		    }
	  case 'S' :{x=a.y-l;while (a.y>x)
			{ a.y--; if (cautarey(a) && cautarex(a)) contor++;}
		     break;
		    }
	  case 'E' :{x=a.x+l;while (a.x<x)
			{ a.x++; if (cautarey(a) && cautarex(a)) contor++;}
		     break;
		    }
	  case 'V' :{x=a.x-l;while (a.x>x)
			{ a.x--; if (cautarey(a) && cautarex(a)) contor++;}
		     break;
		    }
 	}
    }
  printf("%ld",contor);
  return 0;
}