Cod sursa(job #998363)

Utilizator poptibiPop Tiberiu poptibi Data 16 septembrie 2013 20:30:41
Problema Zota & Chidil Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;


const int DX[12] = {-2, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 2};
const int DY[12] = {0, -1, 0, 1, -2, -1, 1, 2, -1, 0, 1, 0};

int N, M, X, Y, Steps;
vector<pair<int, int> > V, OX, OY;
char Dir;

inline int Find(vector<pair<int, int> > V, int X, int Y)
{
    int Pos = 0, Step;
    pair<int, int> Target = make_pair(X, Y);
    if(V.back() <= Target) return V.size();
    for(Step = (1 << 20); Step; Step /= 2)
        if(Pos + Step < V.size() && V[Pos + Step] <= Target)
            Pos += Step;
    return Pos + 1;
}

int main()
{
    ifstream fin("zc.in");
    ofstream fout("zc.out");

    fin >> N >> M;
    for(int i = 1; i <= N; ++ i)
    {
        fin >> X >> Y;
        V.push_back(make_pair(X, Y));
        for(int j = 0; j < 12; ++ j)
            V.push_back(make_pair(X + DX[j], Y + DY[j]));
    }

    sort(V.begin(), V.end());
    if(V[0].first || V[0].second) OX.push_back(V[0]), OY.push_back(make_pair(V[0].second, V[0].first));
    for(int i = 1; i < V.size(); ++ i)
        if(!(V[i].first == 0 && V[i].second == 0) && V[i] != V[i - 1])
            OX.push_back(V[i]), OY.push_back(make_pair(V[i].second, V[i].first));

    sort(OY.begin(), OY.end());

    int X = 0, Y = 0, Ans = 0;

    for(; M; M --)
    {
        fin >> Dir >> Steps;
        int L, R;

        if(Dir == 'N')
        {
            L = Find(OX, X, Y);
            Y += Steps;
            R = Find(OX, X, Y);
        }else if(Dir == 'S')
        {
            R = Find(OX, X, Y - 1);
            Y -= Steps;
            L = Find(OX, X, Y - 1);
        }else if(Dir == 'V')
        {
            R = Find(OY, Y, X - 1);
            X -= Steps;
            L = Find(OY, Y, X - 1);
        }else
        {
            L = Find(OY, Y, X);
            X += Steps;
            R = Find(OY, Y, X);
        }

        Ans += R - L;
    }
    fout << Ans;

    return 0;
}