Cod sursa(job #1565659)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 11 ianuarie 2016 09:29:20
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cctype>
#define MaxB 8192
using namespace std;
int step_count,trap_count,Ptr=0;
char Buf[MaxB];
vector<pair<int,int> > traps,inverted_traps;
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;
}
void check(int x,int y){
    if(x!=0||y!=0)
        traps.push_back(make_pair(x,y));
}
int main(){
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    int x,y,i,dx,dy,step,distance,answer=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();
        check(x,y);
        check(x+1,y);
        check(x-1,y);
        check(x,y-1);
        check(x,y+1);
        check(x-2,y);
        check(x+2,y);
        check(x,y-2);
        check(x,y+2);
        check(x+1,y+1);
        check(x-1,y-1);
        check(x-1,y+1);
        check(x+1,y-1);
    }
    sort(traps.begin(),traps.end());
    trap_count=0;
    for(i=1;i<traps.size();++i)
        if(traps[i]!=traps[i-1]){
            trap_count++;
            traps[trap_count]=traps[i];
        }
    traps.resize(trap_count+1);
    for(i=0;i<trap_count;i++)
        inverted_traps.push_back(make_pair(traps[i].second,traps[i].first));
    sort(inverted_traps.begin(),inverted_traps.end());
    x=y=0;
    for(step=1;step<=step_count;++step){
        direction=GetChar();
        distance=GetInt();
        if(direction=='N'){
            answer=answer+upper_bound(traps.begin(),traps.end(),make_pair(x,y+distance))-lower_bound(traps.begin(),traps.end(),make_pair(x,y+1));
            y+=distance;
        }
        if(direction=='S'){
            answer=answer+upper_bound(traps.begin(),traps.end(),make_pair(x,y-1))-lower_bound(traps.begin(),traps.end(),make_pair(x,y-distance));
            y-=distance;
        }
        if(direction=='E'){
            answer=answer+upper_bound(inverted_traps.begin(),inverted_traps.end(),make_pair(y,x+distance))-lower_bound(inverted_traps.begin(),inverted_traps.end(),make_pair(y,x+1));
            x+=distance;
        }
        if(direction=='V'){
            answer=answer+upper_bound(inverted_traps.begin(),inverted_traps.end(),make_pair(y,x-1))-lower_bound(inverted_traps.begin(),inverted_traps.end(),make_pair(y,x-distance));
            x-=distance;
        }
    }
    printf("%d",answer);
    return 0;
}