Cod sursa(job #1565665)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 11 ianuarie 2016 09:40:57
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cctype>
#define MaxB 8192
#define MAXN 1300010
using namespace std;
int step_count,trap_count,Ptr=0,k=0;
int dx[12]={-2,-1,-1,-1,0,0,0,0,1,1,1,2};
int dy[12]={0,-1,0,1,-2,-1,1,2,-1,0,1,0};
char Buf[MaxB];
pair<int,int> ox[MAXN],oy[MAXN];
int modul(int x){
    if(x<0)
        return -x;
    return x;
}
int GetInt(){
    int Ans = 0, Sign = 1;
    while(!isdigit(Buf[Ptr]) && Buf[Ptr] != '-')
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    while(isdigit(Buf[Ptr]) || Buf[Ptr] == '-')
    {
        if(Buf[Ptr] == '-') Sign = -1;
        else Ans = Ans * 10 + Buf[Ptr] - '0';
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    }
    return Sign * Ans;
}
char GetChar()
{
    char Ans;
    while(!isupper(Buf[Ptr]))
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    while(isupper(Buf[Ptr]))
    {
        Ans = Buf[Ptr];
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    }
    return Ans;
}
int find_trap(pair<int,int> v[MAXN],int x,int y){
    int left=1,right=k,middle;
    pair<int,int> point=make_pair(x,y);
    if(v[k]<=point)
        return k+1;
    while(left<=right){
        middle=(left+right)/2;
        if(v[middle]<=point)
            left=middle+1;
        else
            right=middle-1;
    }
    return left;
}
int main(){
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    int x,y,i,step,distance,answer=0,j,temp=0;
    char enter,direction;
    fread(Buf,1,MaxB,stdin);
    trap_count=GetInt();
    step_count=GetInt();
    for(i=1;i<=trap_count;i++){
        x=GetInt();
        y=GetInt();
        for(j=0;j<12;j++)
            if(x+dx[j]!=0||y+dy[j]!=0)
                ox[++k]=make_pair(x+dx[j],y+dy[j]);
    }
    sort(ox,ox+k+1);
    ox[0].first=ox[1].first-1;
    for(i=1;i<=k;i++)
        if(ox[i]!=ox[i-1]){
            ox[++temp]=ox[i];
            oy[temp]=make_pair(ox[i].second,ox[i].first);
        }
    k=temp;
    sort(oy+1,oy+k+1);
    x=y=0;
    for(step=1;step<=step_count;++step){
        direction=GetChar();
        distance=GetInt();
        if(direction=='N'){
            answer=answer+find_trap(ox,x,y+distance)-find_trap(ox,x,y);
            y+=distance;
        }
        if(direction=='S'){
            answer=answer+find_trap(ox,x,y-1)-find_trap(ox,x,y-distance-1);
            y-=distance;
        }
        if(direction=='E'){
            answer=answer+find_trap(oy,y,x+distance)-find_trap(oy,y,x);
            x+=distance;
        }
        if(direction=='V'){
            answer=answer+find_trap(oy,y,x-1)-find_trap(oy,y,x-distance-1);
            x-=distance;
        }
    }
    printf("%d",answer);
    return 0;
}