Cod sursa(job #998324)

Utilizator poptibiPop Tiberiu poptibi Data 16 septembrie 2013 19:42:11
Problema Zota & Chidil Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <cstdio>
#include <cstdlib>
#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;

int Find(int X1, int Y1, int X2, int Y2)
{
    if(X1 == X2)
    {
        if(Y1 > Y2) swap(Y1, Y2);

        int Left = 0, Right = OX.size() - 1, Mid, AnsLeft = OX.size(), X = X1, AnsRight = -1;
        while(Left <= Right)
        {
            Mid = (Left + Right) / 2;
            if(OX[Mid].first > X || (OX[Mid].first == X && OX[Mid].second >= Y1)) AnsLeft = Mid, Right = Mid - 1;
            else Left = Mid + 1;
        }

        Left = AnsLeft - 1, Right = OX.size() - 1;

        while(Left <= Right)
        {
            Mid = (Left + Right) / 2;
            if(OX[Mid].first < X || (OX[Mid].first == X && OX[Mid].second <= Y2)) AnsRight = Mid, Left = Mid + 1;
            else Right = Mid - 1;
        }

        return AnsRight - AnsLeft + 1;
    }else
    {
        if(X1 > X2) swap(X1, X2);

        int Left = 0, Right = OY.size() - 1, Mid, AnsLeft = OY.size(), Y = Y1, AnsRight = -1;
        while(Left <= Right)
        {
            Mid = (Left + Right) / 2;
            if(OY[Mid].first > Y || (OY[Mid].first == Y && OY[Mid].second >= X1)) AnsLeft = Mid, Right = Mid - 1;
            else Left = Mid + 1;
        }

        Left = AnsLeft - 1, Right = OY.size() - 1;

        while(Left <= Right)
        {
            Mid = (Left + Right) / 2;
            if(OY[Mid].first < Y || (OY[Mid].first == Y && OY[Mid].second <= X2)) AnsRight = Mid, Left = Mid + 1;
            else Right = Mid - 1;
        }

        return AnsRight - AnsLeft + 1;
    }
}

int main()
{
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);

    scanf("%i %i", &N, &M);
    for(int i = 1; i <= N; ++ i)
    {
        scanf("%i %i", &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;

    scanf("\n");
    for(; M; M --)
    {
        scanf("%c %i\n", &Dir, &Steps);
        if(Dir == 'N')
        {
            Ans += Find(X, Y + 1, X, Y + Steps);
            Y += Steps;
        }else if(Dir == 'S')
        {
            Ans += Find(X, Y - 1, X, Y - Steps);
            Y -= Steps;
        }else if(Dir == 'V')
        {
            Ans += Find(X - Steps, Y, X - 1, Steps);
            X -= Steps;
        }else
        {
            Ans += Find(X + 1, Y, X + Steps, Y);
            X += Steps;
        }
    }

    printf("%i\n", Ans);

    return 0;
}