Cod sursa(job #1730658)

Utilizator GoogalAbabei Daniel Googal Data 17 iulie 2016 13:26:57
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#include <algorithm>
#define x first
#define y second
using namespace std;
ifstream fin ("zc.in");
ofstream fout ("zc.out");
int N, M, Px, Py, cx, cy, nrel, nr, dist, s1, s2, sol;
pair < int, int > A[1300000], B[1300000];
char dir;

int Modul(int val)
{
    if (val < 0) val *= -1;
    return val;
}

int Caut_Binar(int X, int Y, pair < int, int > V[])
{
    int p = 1, u = nr, mij;
    pair < int, int > val;
    val.x = X; val.y = Y;

    if (V[nr] <= val) return nr + 1;

    while (p < u)
    {
        mij = (p + u) / 2;
        if (V[mij] <= val) p = mij + 1;
        else u = mij;
    }

    return p;
}

int main()
{
    fin >> N >> M;
    for (int k=1; k<=N; k++)
    {
        fin >> cx >> cy;
        for (int i=-2; i<=2; i++)
        {
            for (int j=-2; j<=2; j++)
            {
                if (Modul(i) + Modul(j) <= 2 && (cx + i || cy + j))
                {
                    A[++nrel].x = cx + i;
                    A[nrel].y = cy + j;
                }
            }
        }
    }

    sort (A + 1, A + 1 + nrel);

    for (int i=1; i<=nrel; i++)
    {
        if (A[i].x != A[i-1].x || A[i].y != A[i-1].y)
        {
            A[++nr] = A[i];
            B[nr].x = A[i].y;
            B[nr].y = A[i].x;
        }
    }

    sort (B + 1, B + 1 + nr);

    for (int i=1; i<=M; i++)
    {
        fin >> dir >> dist;
        switch (dir)
        {
            case 'N' :
            {
                s1 = Caut_Binar(Px, Py, A);
                Py += dist;
                s2 = Caut_Binar(Px, Py, A);
                break;
            }
            case 'S' :
            {
                s2 = Caut_Binar(Px, Py - 1, A);
                Py -= dist;
                s1 = Caut_Binar(Px, Py - 1, A);
                break;
            }
            case 'E' :
            {
                s1 = Caut_Binar(Py, Px, B);
                Px += dist;
                s2 = Caut_Binar(Py, Px, B);
                break;
            }
            case 'V' :
            {
                s2 = Caut_Binar(Py, Px - 1, B);
                Px -= dist;
                s1 = Caut_Binar(Py, Px - 1, B);
                break;
            }
        }

        sol += s2 - s1;
    }

    fout << sol << '\n';
    fout.close();
    return 0;
}