Cod sursa(job #998380)

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

const int NMAX = 1200010;
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, K;
pair<int, int> OX[NMAX], OY[NMAX];
char Dir;

int Find(pair<int, int> V[NMAX], int X, int Y)
{
    int Left = 1, Right = K, Mid;
    pair<int, int> Target = make_pair(X, Y);
    if(V[K] <= Target) return K + 1;

    while(Left <= Right)
    {
        Mid = (Left + Right) / 2;
        if(V[Mid] <= Target) Left = Mid + 1;
        else Right = Mid - 1;
    }
    return Left;
}

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

    fin >> N >> M;

    for(int i = 1; i <= N; ++ i)
    {
        fin >> X >> Y;
        if(X != 0 || Y != 0) OX[++ K] = make_pair(X, Y);
        for(int 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 + 1, OX + K + 1);
    OX[0].first = OX[1].first - 1;

    int KK = 0;
    for(int i = 1; i <= K; ++ i)
        if(OX[i] != OX[i - 1])
        {
            OX[++ KK] = OX[i];
            OY[KK] = make_pair(OX[KK].second, OX[KK].first);
        }

    K = KK;

    sort(OY + 1, OY + K + 1);

    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;
}