Cod sursa(job #3171334)

Utilizator nicushor21Pirlog Marian Nicolae nicushor21 Data 18 noiembrie 2023 18:40:57
Problema Zota & Chidil Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.57 kb
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
struct punct{
    int x,y;
};
int cmp1(punct a,punct b){
    if(a.x==b.x){
        return a.y<b.y;
    }
    return a.x<b.x;
}
int cmp2(punct a,punct b){
    if(a.y==b.y){
        return a.x<b.x;
    }
    return a.y<b.y;
}
int upbX(punct v[],int l,int x){
    int st=1,dr=l,mid,pos=0;
    while(st<=dr){
        mid=(st+dr)/2;
        if(v[mid].x<=x){
            st=mid+1;
            pos=mid;
        }else{
            dr=mid-1;
        }
    }
    return pos;
}
int upbY(punct v[],int l,int x){
    int st=1,dr=l,mid,pos=0;
    while(st<=dr){
        mid=(st+dr)/2;
        if(v[mid].y<=x){
            st=mid+1;
            pos=mid;
        }else{
            dr=mid-1;
        }
    }
    return pos;
}
int lwbX(punct v[],int l,int x){
    int st=1,dr=l,mid,pos=0;
    while(st<=dr){
        mid=(st+dr)/2;
        if(v[mid].x>=x){
            dr=mid-1;
            pos=mid;
        }else{
            st=mid+1;
        }
    }
    return pos;
}
int lwbY(punct v[],int l,int x){
    int st=1,dr=l,mid,pos=0;
    while(st<=dr){
        mid=(st+dr)/2;
        if(v[mid].y>=x){
            dr=mid-1;
            pos=mid;
        }else{
            st=mid+1;
        }
    }
    return pos;
}
punct vx[1300001],vy[1300001];
int c,m,i,j,k,cx,cy,cnt,dist,aux1,aux2,rez;
char dir;
int main(){
    ifstream fin("zc.in");
    ofstream fout("zc.out");
    fin>>c>>m;
    for(i=1;i<=c;i++){
        fin>>cx>>cy;
        for(j=-2;j<=2;j++){
            for(k=-2;k<=2;k++){
                if(abs(j)+abs(k)<=2){
                    if(cx+j!=0||cy+k!=0){  
                        vx[++cnt]={cx+j,cy+k};
                        vy[cnt]={cx+j,cy+k};
                    }
                }
            }
        }
    }
    sort(vx+1,vx+cnt+1,cmp1);
    sort(vy+1,vy+cnt+1,cmp2);
    int crtx=0,crty=0;
    for(j=1;j<=m;j++){
        fin>>dir>>dist;
        if(dir=='N'){
            aux1=lwbX(vx,cnt,crtx);
            aux2=upbX(vx,cnt,crtx);
            if(aux2!=0&&aux1!=0){
                for(i=aux1;i<=aux2;i++){
                    if(vx[i].y>crty&&vx[i].y<=crty+dist&&vx[i].y!=0&&vx[i].y!=vx[i-1].y){
                        rez++;
                    }
                }
            }
            crty+=dist;
        }
        if(dir=='S'){
            aux1=lwbX(vx,cnt,crtx);
            aux2=upbX(vx,cnt,crtx);
            if(aux2!=0&&aux1!=0){
                for(i=aux1;i<=aux2;i++){
                    if(vx[i].y<crty&&vx[i].y>=crty-dist&&vx[i].y!=0&&vx[i].y!=vx[i-1].y){
                        rez++;
                    }
                }
            }
            crty-=dist;
        }
        if(dir=='V'){
            aux1=lwbY(vy,cnt,crty);
            aux2=upbY(vy,cnt,crty);
            if(aux2!=0&&aux1!=0){
                for(i=aux1;i<=aux2;i++){
                    if(vy[i].x<crtx&&vy[i].x>=crtx-dist&&vy[i].x!=0&&vy[i].x!=vy[i-1].x){
                        rez++;
                    }
                }
            }
            crtx-=dist;
        }
        if(dir=='E'){
            aux1=lwbY(vy,cnt,crty);
            aux2=upbY(vy,cnt,crty);
            if(aux2!=0&&aux1!=0){
                for(i=aux1;i<=aux2;i++){
                    if(vy[i].x>crtx&&vy[i].x<=crtx+dist&&vy[i].x!=0&&vy[i].x!=vy[i-1].x){
                        rez++;
                    }
                }
            }
            crtx+=dist;
        }
    }
    fout<<rez;
    fin.close();
    fout.close();
    return 0;
}