Cod sursa(job #1724358)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 2 iulie 2016 22:03:47
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.53 kb
#include <cstdio>
#include <algorithm>
#define MAXN 100000
#define MAXDIST 2
FILE*fi,*fout;
class Point{
   public :
    int x;
    int y;
};
Point V[13*MAXN+1];
char dublu[13*MAXN+1];
bool cmp1(Point a,Point b){
    if(a.x==b.x)
      return a.y<b.y;
    return a.x<b.x;
}
class Segmentx{
  public :
    int x;
    int y1;
    int y2;
};
Segmentx Sx[MAXN+1];
bool cmp2(Segmentx a,Segmentx b){
   return a.x<b.x;
}
class Segmenty{
  public :
    int y;
    int x1;
    int x2;
};
Segmenty Sy[MAXN+1];
bool cmp3(Segmenty a,Segmenty b){
   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);
}
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;
    }
}
#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{
      while(a<'0'||a>'9')
        a=nextch();
      int nr=0;
      while(a>='0'&&a<='9'){
        nr=nr*10+a-'0';
        a=nextch();
      }
      return nr;
   }
}
int main(){
    int n,m,x,y,i,j,ix,iy,x1,x2,y1,y2,con,l,rez,pas,conx,cony;
    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++;
             V[con].x=x+ix;
             V[con].y=y+iy;
          }
    }
    std::sort(V+1,V+con+1,cmp1);
    i=1;
    while(i<=13*n){
       j=i+1;
       while(j<=13*n&&V[i].x==V[j].x&&V[i].y==V[j].y){
          dublu[j]=1;
          j++;
       }
       i=j;
    }
    x1=y1=0;
    x2=y2=0;
    conx=cony=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'){
           conx++;
           Sx[conx].x=x1;
           Sx[conx].y1=y1;
           Sx[conx].y2=y2;
        }
        else{
           cony++;
           Sy[cony].y=y1;
           Sy[cony].x1=x1;
           Sy[cony].x2=x2;
        }
        x1=x2;
        y1=y2;
    }
    std::sort(Sx+1,Sx+conx+1,cmp2);
    std::sort(Sy+1,Sy+cony+1,cmp3);
    con=0;
    for(i=1;i<=13*n;i++)
     if(dublu[i]==0&&!(V[i].x==0&&V[i].y==0)){
        rez=0;
        for(pas=1<<16;pas;pas>>=1)
          if(rez+pas<=conx&&V[i].x>Sx[rez+pas].x)
            rez+=pas;
        rez++;
        while(rez<=conx&&V[i].x==Sx[rez].x){
           if(good(Sx[rez].x,Sx[rez].y1,Sx[rez].x,Sx[rez].y2,V[i].x,V[i].y)==1)
             con++;
           rez++;
        }
        rez=0;
        for(pas=1<<16;pas;pas>>=1)
          if(rez+pas<=cony&&V[i].y>Sy[rez+pas].y)
            rez+=pas;
        rez++;
        while(rez<=cony&&V[i].y==Sy[rez].y){
           if(good(Sy[rez].x1,Sy[rez].y,Sy[rez].x2,Sy[rez].y,V[i].x,V[i].y)==1)
             con++;
           rez++;
        }
     }
    fprintf(fout,"%d" ,con);
    fclose(fi);
    fclose(fout);
    return 0;
}