Cod sursa(job #1110869)

Utilizator PatrikStepan Patrik Patrik Data 18 februarie 2014 14:09:55
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
    #include<cstdio>
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    #define PII pair<int,int>
    #define mp make_pair
    #define pb push_back
    vector<PII> v,u;
    int N , M , n , X , Y , sol;

    void read();
    int abs(int k)
    {
        if(k < 0)return -k;
        return k;
    }
    void solve();
    void write();

    int main()
    {
        read();
        solve();
        write();
        return 0;
    }

    void read()
    {
        int x , y;
        freopen("zc.in" , "r" , stdin );
        scanf("%d%d" , &N , &M );
        for(int i = 1 ; i <= N ; ++i )
        {
            scanf("%d%d\n" , &x , &y );
            for(int k = -2 ; k <= 2 ; ++k )
                for(int p = -2 ; p <= 2 ; ++p )
                    if(abs(k)+abs(p) <= 2)
                        v.pb(mp(x+k,y+p));
        }
    }

    void solve()
    {
        char c;
        int d;
        sort(v.begin(),v.end());
        v.resize(unique(v.begin() , v.end()) - v.begin());
        n = 0;
        for(int i = 1 ; i < (int)v.size() ; ++i )
            if(v[i] != v[i-1])
                v[++n] = v[i];
        v.resize(n+1);
        u.resize(n+1);
        for(int i = 0 ; i < (int)v.size() ; ++i )
            u[i] = mp(v[i].second , v[i].first);
        sort(u.begin(),u.end());
        for(int i = 1 ; i <= M ; ++i )
        {
            scanf("%c %d\n" , &c , &d );
            if(c == 'N')
            {
                sol+=upper_bound(v.begin(),v.end(),mp(X,Y+d))-lower_bound(v.begin(),v.end(),mp(X,Y+1));
                Y+=d;
                continue;
            }
            if(c == 'S')
            {
                sol+=upper_bound(v.begin(),v.end(),mp(X,Y-1))-lower_bound(v.begin(),v.end(),mp(X,Y-d));
                Y-=d;
                continue;
            }
            if(c == 'E')
            {
                sol+=upper_bound(u.begin(),u.end(),mp(Y,X+d))-lower_bound(u.begin(),u.end(),mp(Y,X+1));
                X+=d;
                continue;
            }
            if(c =='V')
            {
                sol+=upper_bound(u.begin(),u.end(),mp(Y,X-1))-lower_bound(u.begin(),u.end(),mp(Y,X-d));
                X-=d;
            }
        }
    }

    void write()
    {
        freopen("zc.out" , "w" , stdout );
        printf("%d" , sol);
   }