Cod sursa(job #1724375)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 2 iulie 2016 22:52:08
Problema Zota & Chidil Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.69 kb
#include <cstdio>
#include <algorithm>
#define MAXN 100000
#define MAXDIST 2
FILE*fi,*fout;
class Point{
   public :
    int x;
    int y;
};
Point Vx[13*MAXN+1],Vy[13*MAXN+1],vx[13*MAXN+1],vy[13*MAXN+1];
char dublux[13*MAXN+1],dubluy[13*MAXN+1];
bool cmp1(Point a,Point b){
    if(a.x==b.x)
      return a.y<b.y;
    return a.x<b.x;
}
bool cmp2(Point a,Point b){
    if(a.y==b.y)
      return a.x<b.x;
    return a.y<b.y;
}
#define MAXBUF (1<<20)
char buf[MAXBUF];
int pos=MAXBUF;
inline char nextch(){
    if(pos==MAXBUF){
        fread(buf,1,MAXBUF,fi);
        pos=0;
    }
    return buf[pos++];
}
inline int getnr(){
   char a=nextch();
   if(a=='N'||a=='S'||a=='V'||a=='E')
     return a;
   else{
      int semn=1;
      if(a=='-')
        semn=-1;
      while(a<'0'||a>'9')
        a=nextch();
      int nr=0;
      while(a>='0'&&a<='9'){
        nr=nr*10+a-'0';
        a=nextch();
      }
      return nr*semn;
   }
}
inline int myabs(int x){
   if(x<0)
     x=-x;
   return x;
}
int main(){
    int i,j,n,m,ix,iy,l,conx,cony,rez1,rez2,pas,x,y,x1,y1,x2,y2,x11,y11,x22,y22;
    long long con;
    char dir;
    fi=fopen("zc.in" ,"r");
    fout=fopen("zc.out" ,"w");
    n=getnr();
    m=getnr();
    con=0;
    for(i=1; i<=n; i++){
        x=getnr();
        y=getnr();
        for(ix=-2;ix<=2;ix++)
         for(iy=-2;iy<=2;iy++)
           if(myabs(ix)+myabs(iy)<=MAXDIST){
             con++;
             Vx[con].x=x+ix;
             Vx[con].y=y+iy;
             Vy[con].x=Vx[con].x;
             Vy[con].y=Vx[con].y;
          }
    }
    std::sort(Vx+1,Vx+con+1,cmp1);
    std::sort(Vy+1,Vy+con+1,cmp2);
    i=1;
    while(i<=13*n){
       j=i+1;
       while(j<=13*n&&Vx[i].x==Vx[j].x&&Vx[i].y==Vx[j].y){
          dublux[j]=1;
          j++;
       }
       i=j;
    }
    conx=0;
    for(i=1;i<=13*n;i++)
      if(dublux[i]==0){
         conx++;
         vx[conx]=Vx[i];
      }
    i=1;
    while(i<=13*n){
       j=i+1;
       while(j<=13*n&&Vy[i].x==Vy[j].x&&Vy[i].y==Vy[j].y){
          dubluy[j]=1;
          j++;
       }
       i=j;
    }
    cony=0;
    for(i=1;i<=13*n;i++)
      if(dubluy[i]==0){
         cony++;
         vy[cony]=Vy[i];
      }
    x1=y1=0;
    x2=y2=0;
    con=0;
    for(i=1;i<=m;i++){
       dir=getnr();
       l=getnr();
        if(dir=='N'){
            y2+=l;
            y1++;
        }
        if(dir=='S'){
            y2-=l;
            y1--;
        }
        if(dir=='E'){
            x2+=l;
            x1++;
        }
        if(dir=='V'){
            x2-=l;
            x1--;
        }
        if(dir=='N'||dir=='S'){
         if(y1>y2){
             y11=y2;
             y22=y1;
          }
          else{
             y11=y1;
             y22=y2;
          }
          rez1=0;
          for(pas=1<<16;pas;pas>>=1)
            if(rez1+pas<=conx&&(vx[rez1+pas].x<x1||(vx[rez1+pas].x==x1&&vx[rez1+pas].y<y11)))
              rez1+=pas;
          rez2=0;
          for(pas=1<<16;pas;pas>>=1)
            if(rez2+pas<=conx&&(vx[rez2+pas].x<x1||(vx[rez2+pas].x==x1&&vx[rez2+pas].y<=y22)))
              rez2+=pas;
           con=con+rez2-rez1;
        }
        else{
          if(x1>x2){
             x11=x2;
             x22=x1;
          }
          else{
             x11=x1;
             x22=x2;
          }
          rez1=0;
          for(pas=1<<16;pas;pas>>=1)
            if(rez1+pas<=cony&&(vy[rez1+pas].y<y1||(vy[rez1+pas].y==y1&&vy[rez1+pas].x<x11)))
              rez1+=pas;
          rez2=0;
          for(pas=1<<16;pas;pas>>=1)
            if(rez2+pas<=cony&&(vy[rez2+pas].y<y1||(vy[rez2+pas].y==y1&&vy[rez2+pas].x<=x22)))
              rez2+=pas;
           con=con+rez2-rez1;
        }
        x1=x2;
        y1=y2;
    }
    fprintf(fout,"%lld" ,con);
    fclose(fi);
    fclose(fout);
    return 0;
}