Cod sursa(job #1724329)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 2 iulie 2016 21:09:08
Problema Zota & Chidil Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.68 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[16],cop[16];
inline int cauta(int x,int y){
    int i=0;
    while(i<16&&!(cod[i].x==x&&cod[i].y==y))
        i++;
    if(x==0&&y==0)
        return 0;
    return (i==16);
}
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,j,e;
    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
  //  for(i=1; i<=n; i++)
   //     printf("%d %d\n" ,C1[i].x,C1[i].y);
  //  printf("\n");
    x1=y1=0;
    x2=y2=0;
    con=0;
    while(m>0){
        m--;
        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++;
            e=0;
            while(rez<=n&&myabs(x1-C1[rez].x)<=MAXDIST){
                ind=0;
                for(j=-2; j<=2; j++){
                    d=dist(C1[rez].x,C1[rez].y,x1,C1[rez].y+j);
                    if(d<=MAXDIST&&good(x1,y1,x2,y2,x1,C1[rez].y+j)){
                        if(C1[rez].y+j!=y1&&cauta(x1,C1[rez].y+j)==1){
                            con++;
                            cop[ind].x=x1;
                            cop[ind].y=C1[rez].y+j;
                            ind++;
                        }
                    }
                }
                for(i=0; i<ind; i++){
                    cod[(i+e)%16].x=cop[i].x;
                    cod[(i+e)%16].y=cop[i].y;
                }
                e=(e+ind)%16;
                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;
                for(j=-2; j<=2; j++){
                    d=dist(C2[rez].x,C2[rez].y,C2[rez].x+j,y1);
                    if(d<=MAXDIST&&good(x1,y1,x2,y2,C2[rez].x+j,y1)){
                        if(C2[rez].x+j!=x1&&cauta(C2[rez].x+j,y1)==1){
                            con++;
                            cop[ind].x=C2[rez].x+j;
                            cop[ind].y=y1;
                            ind++;
                        }
                    }
                }
                for(i=0; i<ind; i++){
                    cod[(i+e)%16].x=cop[i].x;
                    cod[(i+e)%16].y=cop[i].y;
                }
                e=(e+ind)%16;
                rez++;
            }
        }
        x1=x2;
        y1=y2;
    }
    fprintf(fout,"%d" ,con);
    fclose(fi);
    fclose(fout);
    return 0;
}