Cod sursa(job #998333)

Utilizator poptibiPop Tiberiu poptibi Data 16 septembrie 2013 19:52:30
Problema Zota & Chidil Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.45 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;

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

      //  if(!(OX[AnsLeft].first == X && Y1 <= OX[AnsLeft].first && OX[AnsLeft].first <= Y2)) return 0;

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

      //  if(!(OX[AnsRight].first == X && Y1 <= OX[AnsRight].first && OX[AnsRight].first <= Y2)) return 0;

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

        //if(!(OY[AnsLeft].first == Y && X1 <= OY[AnsLeft].first && OY[AnsLeft].first <= X2)) return 0;
        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;
        }

        //if(!(OY[AnsRight].first == Y && X1 <= OY[AnsRight].first && OY[AnsRight].first <= X2)) return 0;

        return AnsRight - AnsLeft + 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;
        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;
        }
    }

    fout << Ans;

    return 0;
}