Cod sursa(job #1565641)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 11 ianuarie 2016 09:08:21
Problema Zota & Chidil Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int step_count,trap_count;
vector<pair<int,int> > traps,inverted_traps;
int modul(int x){
    if(x<0)
        return -x;
    return x;
}
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;
    scanf("%d%d",&trap_count,&step_count);
    for(i=1;i<=trap_count;i++){
        scanf("%d%d",&x,&y);
        for(dx=-2;dx<=2;dx++)
            for(dy=-2;dy<=2;dy++)
                if(modul(dx)+modul(dy)<=2&&(x+dx!=0||y+dy!=0))
                    traps.push_back(make_pair(x+dx,y+dy));
    }
    scanf("%c",&enter);
    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];
        }
    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++){
        scanf("%c%d%c",&direction,&distance,&enter);
        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;
}