Cod sursa(job #1724300)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 2 iulie 2016 19:28:32
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.16 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){
   return a.x<b.x;
}
bool cmp2(Capcana a,Capcana b){
   return a.y<b.y;
}
inline long long myabs(long long x){
    if(x<0)
      x=-x;
    return x;
}
inline long long dist(long long x1,long long y1,long long x2,long long y2){
     return myabs(x1-x2)+myabs(y1-y2);
}
int main(){
   FILE*fi,*fout;
   int x,y,con,i,l,rez,pas,x1,x2,y1,y2,n,m;
   long long 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(i=0;i<m;i++){
      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){
             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)
                       con++;
                 }
                 d=dist(C1[rez].x,C1[rez].y,x1,C1[rez].y-1);
                 if(d<=MAXDIST){
                    if(C1[rez].y-1!=y1)
                       con++;
                 }
                 d=dist(C1[rez].x,C1[rez].y,x1,C1[rez].y+1);
                 if(d<=MAXDIST){
                    if(C1[rez].y+1!=y1)
                       con++;
                 }
             }
             else{
                 d=dist(C1[rez].x,C1[rez].y,x2,y2);
                 if(d<=MAXDIST)
                    con++;
             }
             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){
             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)
                       con++;
                 }
                 d=dist(C2[rez].x,C2[rez].y,C2[rez].x-1,y1);
                 if(d<=MAXDIST){
                    if(C2[rez].x-1!=x1)
                       con++;
                 }
                 d=dist(C2[rez].x,C2[rez].y,C2[rez].x+1,y);
                 if(d<=MAXDIST){
                    if(C2[rez].x+1!=x1)
                       con++;
                 }
             }
             else{
                 d=dist(C2[rez].x,C2[rez].y,x2,y2);
                 if(d<=MAXDIST)
                    con++;
             }
             rez++;
         }
      }
      x1=x2;
      y1=y2;
   }
   fprintf(fout,"%d" ,con);
   fclose(fi);
   fclose(fout);
   return 0;
}