Cod sursa(job #196962)

Utilizator katakunaCazacu Alexandru katakuna Data 30 iunie 2008 14:09:22
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.2 kb
#include<stdio.h>
#include<algorithm>
#define INF 2000003
using namespace std;

struct zc {int x,y;}vx[1300001],vy[1300001];

int D,P,q,w,n,m,i,j,x,y,a,b,k;
int d[2][13]={{0,0,0,0,0,1,1,1,2,-1,-1,-1,-2},{-2,-1,0,1,2,-1,0,1,0,-1,0,1,0}};


int cmpy(zc a,zc b){

if(a.y < b.y)
return 1;

  if(a.y == b.y ){

    if(a.x < b.x){
    return 1;
    }


  }

return 0;
}


int cmpx(zc a,zc b){

if(a.x < b.x)
return 1;

  if(a.x == b.x ){

    if(a.y < b.y){
    return 1;
    }


  }

return 0;
}


int main(){


FILE *f=fopen("zc.in","r");

fscanf(f,"%d %d",&n,&m);

  for(i=1;i<=n;i++){
  fscanf(f,"%d %d",&x,&y);
    for(j=0;j<=12;j++){
    a=x+d[0][j];
    b=y+d[1][j];

     k++;
     vx[k].x=a;
     vx[k].y=b;


    }
  }

sort(vx+1,vx+k+1,cmpx);


int r;
for(i=1;i<=k;i++){

 if(vx[i].x==vx[i+1].x && vx[i].y==vx[i+1].y ){
 vx[i].x=INF;
 }

}

sort(vx+1,vx+k+1,cmpx);

  for(i=k;i>=1;i--){
   if(vx[i].x==INF)
   k--;
   else
   break;
  }

  for(i=1;i<=k;i++){
  vy[i].x=vx[i].x;
  vy[i].y=vx[i].y;
  }

sort(vy+1,vy+k+1,cmpy);

int nr=0;
x=y=0;
int p,u,mij;

fscanf(f,"\n");
char D;

///////////////////////////////////////////////////
x=0;
y=0;

  for(i=1;i<=m;i++){
  fscanf(f,"%c %d\n",&D,&P);

    if(D=='N'){
    //caut x x+1
    p=1;
    u=k;

      while(p<=u){
      mij=(p+u)/2;

         if(x<=vx[mij].x)
         u=mij-1;

         else
         p=mij+1;

      }
    

     if(vx[p].x==x){
     a=p;
     p=1;
     u=k;

      while(p<=u){
      mij=(p+u)/2;

         if(x+1<=vx[mij].x)
         u=mij-1;

         else
         p=mij+1;

      }
      
      b=p;

      if(vx[p].x == x+1)
      b--;
      


    //cautam pe y si y+p;
    p=a;
    u=b;

      while(p<=u){
      mij=(p+u)/2;

         if(y+1<=vx[mij].y)
         u=mij-1;

         else
         p=mij+1;

      }

     q=p;



     p=a;
     u=b;

      while(p<=u){
      mij=(p+u)/2;

         if(y+P<=vx[mij].y)
         u=mij-1;

         else
         p=mij+1;

      }

     w=p;

      if(vx[p].y != y+P)
      w--;

       if(w>=q){
       nr+=w-q+1;
       }
      
     }

    y+=P;
    }


    if(D=='S'){
    //caut x si x+1
    //caut x x+1
    p=1;
    u=k;

      while(p<=u){
      mij=(p+u)/2;

         if(x<=vx[mij].x)
         u=mij-1;

         else
         p=mij+1;

      }
    

     if(vx[p].x==x){
     a=p;
     p=1;
     u=k;

      while(p<=u){
      mij=(p+u)/2;

         if(x+1<=vx[mij].x)
         u=mij-1;

         else
         p=mij+1;

      }
      
      b=p;

      if(vx[p].x == x+1)
      b--;
      


    //cautam pe y si y+p;
    p=a;
    u=b;

      while(p<=u){
      mij=(p+u)/2;

         if(y-P<=vx[mij].y)
         u=mij-1;

         else
         p=mij+1;

      }

     q=p;



     p=a;
     u=b;

      while(p<=u){
      mij=(p+u)/2;

         if(y-1<=vx[mij].y)
         u=mij-1;

         else
         p=mij+1;

      }

     w=p;

      if(vx[p].y != y-1)
      w--;

       if(w>=q){
       nr+=w-q+1;
       }
      
     }

    y-=P;
    
    }

    if(D=='E'){
    //cautam pe y
    p=1;
    u=k;

      while(p<=u){
      mij=(p+u)/2;

         if(y<=vy[mij].y)
         u=mij-1;

         else
         p=mij+1;

      }
    

     if(vy[p].y==y){
     a=p;
     p=1;
     u=k;

      while(p<=u){
      mij=(p+u)/2;

         if(y+1<=vy[mij].y)
         u=mij-1;

         else
         p=mij+1;

      }
      
      b=p;

      if(vy[p].y == y+1)
      b--;


    //cautam pe x si x+p;
    p=a;
    u=b;

      while(p<=u){
      mij=(p+u)/2;

         if(x+1<=vy[mij].x)
         u=mij-1;

         else
         p=mij+1;

      }

     q=p;



     p=a;
     u=b;

      while(p<=u){
      mij=(p+u)/2;

         if(x+P<=vy[mij].x)
         u=mij-1;

         else
         p=mij+1;

      }

     w=p;

      if(vy[p].x != x+P)
      w--;

       if(w>=q){
       nr+=w-q+1;
       }
      
     }

    x+=P;
    }



    if(D=='V'){
    //cautam pe y
    p=1;
    u=k;

      while(p<=u){
      mij=(p+u)/2;

         if(y<=vy[mij].y)
         u=mij-1;

         else
         p=mij+1;

      }
    

     if(vy[p].y==y){
     a=p;
     p=1;
     u=k;

      while(p<=u){
      mij=(p+u)/2;

         if(y+1<=vy[mij].y)
         u=mij-1;

         else
         p=mij+1;

      }
      
      b=p;

      if(vy[p].y == y+1)
      b--;


    //cautam pe x si x+p;
    p=a;
    u=b;

      while(p<=u){
      mij=(p+u)/2;

         if(x-P<=vy[mij].x)
         u=mij-1;

         else
         p=mij+1;

      }

     q=p;



     p=a;
     u=b;

      while(p<=u){
      mij=(p+u)/2;

         if(x-1<=vy[mij].x)
         u=mij-1;

         else
         p=mij+1;

      }

     w=p;

      if(vy[p].x != x-1)
      w--;

       if(w>=q){
       nr+=w-q+1;
       }
      
     }

    x-=P;
    }

  }


fclose(f);

FILE *g=fopen("zc.out","w");
fprintf(g,"%d",nr);
fclose(g);

return 0;
}