Cod sursa(job #1724311)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 2 iulie 2016 20:14:40
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.49 kb
#include <cstdio>
#include <algorithm>
#define MAXN 100000
#define MAXDIST 2
class Capcana{
  public :
    int x;
    int y;
};
Capcana C1[MAXN+1],C2[MAXN+1];
bool cmp1(Capcana a,Capcana b){
   if(a.x==b.x)
     return a.y<b.y;
   return a.x<b.x;
}
bool cmp2(Capcana a,Capcana b){
   if(a.y==b.y)
     return a.x<b.x;
   return a.y<b.y;
}
inline int myabs(int x){
    if(x<0)
      x=-x;
    return x;
}
inline int dist(int x1,int y1,int x2,int y2){
     return myabs(x1-x2)+myabs(y1-y2);
}
Capcana cod[MAXDIST+1],cop[MAXDIST+1];
inline int cauta(int x,int y){
    int i=0;
    while(i<3&&!(cod[i].x==x&&cod[i].y==y))
      i++;
    if(x==0&&y==0)
       return 0;
    return (i==3);
}
inline int good(int x1,int y1,int x2,int y2,int x,int y){
    if(y1==y2){
        if(y==y1&&(x1<=x&&x<=x2)||(x2<=x&&x<=x1))
          return 1;
        return 0;
    }
    else{
        if(x==x1&&(y1<=y&&y<=y2)||(y2<=y&&y<=y1))
          return 1;
        return 0;
    }
}
int main(){
   FILE*fi,*fout;
   int x,y,con,i,l,rez,pas,x1,x2,y1,y2,n,m,ind,d;
   char dir;
   fi=fopen("zc.in" ,"r");
   fout=fopen("zc.out" ,"w");
   fscanf(fi,"%d %d " ,&n,&m);
   for(i=1;i<=n;i++){
       fscanf(fi,"%d %d " ,&x,&y);
       C1[i].x=C2[i].x=x;
       C1[i].y=C2[i].y=y;
   }
   std::sort(C1+1,C1+n+1,cmp1);// x
   std::sort(C2+1,C2+n+1,cmp2);// y
   x1=y1=0;
   x2=y2=0;
   con=0;
   for(int j=0;j<m;j++){
      fscanf(fi,"%c %d " ,&dir,&l);
      if(dir=='N')
        y2+=l;
      if(dir=='S')
        y2-=l;
      if(dir=='E')
        x2+=l;
      if(dir=='V')
        x2-=l;
      if(dir=='N'||dir=='S'){
         rez=0;
         for(pas=1<<16;pas;pas>>=1)
          if(rez+pas<=n&&C1[rez+pas].x<x1-2)
            rez+=pas;
         rez++;
         while(rez<=n&&myabs(x1-C1[rez].x)<=MAXDIST){
             ind=0;
             if((y1<=C1[rez].y&&C1[rez].y<=y2)||(y1>=C1[rez].y&&C1[rez].y>=y2)){
                 d=dist(C1[rez].x,C1[rez].y,x1,C1[rez].y);
                 if(d<=MAXDIST){
                    if(C1[rez].y!=y1&&cauta(x1,C1[rez].y)==1){
                       con++;
                       cop[ind].x=x1;
                       cop[ind].y=C1[rez].y;
                       ind++;
                    }
                 }
                 d=dist(C1[rez].x,C1[rez].y,x1,C1[rez].y-1);
                 if(d<=MAXDIST&&good(x1,y1,x2,y2,x1,C1[rez].y-1)){
                    if(C1[rez].y-1!=y1&&cauta(x1,C1[rez].y-1)==1){
                       con++;
                       cop[ind].x=x1;
                       cop[ind].y=C1[rez].y-1;
                       ind++;
                    }
                 }
                 d=dist(C1[rez].x,C1[rez].y,x1,C1[rez].y+1);
                 if(d<=MAXDIST&&good(x1,y1,x2,y2,x1,C1[rez].y+1)){
                    if(C1[rez].y+1!=y1&&cauta(x1,C1[rez].y+1)==1){
                       con++;
                       cop[ind].x=x1;
                       cop[ind].y=C1[rez].y+1;
                       ind++;
                    }
                 }
             }
             else{
                  d=dist(C1[rez].x,C1[rez].y,x2,y2);
                  if(d<=MAXDIST&&cauta(x2,y2)==1){
                     con++;
                     cop[ind].x=x2;
                     cop[ind].y=y2;
                     ind++;
                  }
             }
             for(i=0;i<=MAXDIST;i++){
                cod[i].x=0;
                cod[i].y=0;
             }
             for(i=0;i<ind;i++){
                cod[i].x=cop[i].x;
                cod[i].y=cop[i].y;
             }
             rez++;
         }
      }
      else{
         rez=0;
         for(pas=1<<16;pas;pas>>=1)
          if(rez+pas<=n&&C2[rez+pas].y<y1-2)
            rez+=pas;
         rez++;
         while(rez<=n&&myabs(y1-C2[rez].y)<=MAXDIST){
             ind=0;
             if((x1<=C2[rez].x&&C2[rez].x<=x2)||(x1>=C2[rez].x&&C2[rez].x>=x2)){
                 d=dist(C2[rez].x,C2[rez].y,C2[rez].x,y1);
                 if(d<=MAXDIST){
                    if(C2[rez].x!=x1&&cauta(C2[rez].x,y1)==1){
                       con++;
                       cop[ind].x=C2[rez].x;
                       cop[ind].y=y1;
                       ind++;
                    }
                 }
                 d=dist(C2[rez].x,C2[rez].y,C2[rez].x-1,y1);
                 if(d<=MAXDIST&&good(x1,y1,x2,y2,C2[rez].x-1,y1)){
                    if(C2[rez].x-1!=x1&&cauta(C2[rez].x-1,y1)==1){
                       con++;
                       cop[ind].x=C2[rez].x-1;
                       cop[ind].y=y1;
                       ind++;
                    }
                 }
                 d=dist(C2[rez].x,C2[rez].y,C2[rez].x+1,y1);
                 if(d<=MAXDIST&&good(x1,y1,x2,y2,C2[rez].x+1,y1)){
                    if(C2[rez].x+1!=x1&&cauta(C2[rez].x+1,y1)==1){
                       con++;
                       cop[ind].x=C2[rez].x+1;
                       cop[ind].y=y1;
                       ind++;
                    }
                 }
             }
             else{
                  d=dist(C2[rez].x,C2[rez].y,x2,y2);
                  if(d<=MAXDIST&&cauta(x2,y2)==1){
                     con++;
                     cop[ind].x=x2;
                     cop[ind].y=y2;
                     ind++;
                  }
             }
             for(i=0;i<=MAXDIST;i++){
                cod[i].x=0;
                cod[i].y=0;
             }
             for(i=0;i<ind;i++){
                cod[i].x=cop[i].x;
                cod[i].y=cop[i].y;
             }
             rez++;
         }
      }
      x1=x2;
      y1=y2;
   }
   fprintf(fout,"%d" ,con);
   fclose(fi);
   fclose(fout);
   return 0;
}