Cod sursa(job #1571736)

Utilizator DiClauDan Claudiu DiClau Data 18 ianuarie 2016 14:17:10
Problema Zota & Chidil Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.22 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N = 100005, P = 17;
const long long LIM = 2000000000;

bool inMatrice (int x, int y)
{
    if (x < -LIM || x > LIM || y < -LIM || y > LIM)
        return false;
    return true;
}
struct capcane
{
    int x, y;
};
capcane v[14 * N], aux[14 * N];
int sfv, ct;
bool cmp1 (capcane a, capcane b)
{
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    if (a.y < b.y)
        return true;
    return false;
}
bool cmp2 (capcane a, capcane b)
{
    if (a.y < b.y)
        return true;
    if (a.y > b.y)
        return false;
    if (a.x < b.x)
        return true;
    return false;
}
void completeaza (int x, int y)
{
    int i;
    v[++sfv].x = x;
    v[sfv].y = y - 2;

    v[++sfv].x = x;
    v[sfv].y = y + 2;

    for (i = x - 1; i <= x + 1; i++)
    {
        v[++sfv].x = i;
        v[sfv].y = y - 1;
        v[++sfv].x = i;
        v[sfv].y = y + 1;
    }
    for (i = x - 2; i <= x + 2; i++)
    {
        v[++sfv].x = i;
        v[sfv].y = y;
    }
}
void elimina ()
{
    int i;
    for (i = 1; i <= sfv; i++)
        if ((v[i].x != v[i - 1].x || v[i].y != v[i - 1].y) && (v[i].x != 0 || v[i].y != 0))
        {
            aux[++ct].x = v[i].x;
            aux[ct].y = v[i].y;
        }
}
void dubleaza ()
{
    int i;
    for (i = 1; i <= ct; i++)
        v[i] = aux[i];
}
int cautBinLinieAux (int start, int n, int x, int cerinta)
{
    int sol = 1 << P, pas = start;
    x += cerinta;
    while (sol > 0)
    {
        if (pas + sol <= n && aux[pas + sol].x < x)
            pas += sol;
        sol >>= 1;
    }
    return pas;
}
int cautBinColoanaAux (int start, int n, int x, int cerinta)
{
    int sol = 1 << P, pas = start;
    x += cerinta;
    while (sol > 0)
    {
        if (pas + sol <= n && aux[pas + sol].y < x)
            pas += sol;
        sol >>= 1;
    }
    return pas;
}
int cautBinLinieV (int start, int n, int x, int cerinta)
{
    int sol = 1 << P, pas = start;
    x += cerinta;
    while (sol > 0)
    {
        if (pas + sol <= n && v[pas + sol].x < x)
            pas += sol;
        sol >>= 1;
    }
    return pas;
}
int cautBinColoanaV (int start, int n, int x, int cerinta)
{
    int sol = 1 << P, pas = start;
    x += cerinta;
    while (sol > 0)
    {
        if (pas + sol <= n && v[pas + sol].y < x)
            pas += sol;
        sol >>= 1;
    }
    return pas;
}
int main ()
{
    FILE *in, *out;
    in = fopen ("zc.in", "r");
    out = fopen ("zc.out", "w");
    int n, m;
    fscanf (in, "%d%d", &n, &m);
    int x, y, i;
    for (i = 1; i <= n; i++)
    {
        fscanf (in, "%d%d", &y, &x);
        completeaza (x, y);
    }
    sort (v + 1, v + sfv + 1, cmp1);
    elimina();
    dubleaza();
    sort (v + 1, v + ct + 1, cmp2);
    fscanf (in, "%d", &m);
    int pasi, rez = 0, start, sfarsit;
    char dir;
    x = 0; y = 0;
    for (i = 1; i <= m; i++)
    {
        fscanf (in, "\n%c%d", &dir, &pasi);
        if (dir == 'N')
        {
            start = cautBinColoanaV (0, ct, y, 0);
            sfarsit = cautBinColoanaV (0, ct, y, 1);
            rez += -cautBinLinieV (start, sfarsit, x + 1, 0) + cautBinLinieV (start, sfarsit, x + pasi, 0);
            x += pasi;
        }
        if (dir == 'S')
        {
            start = cautBinColoanaV (0, ct, y, 0);
            sfarsit = cautBinColoanaV (0, ct, y, 1);
            rez += -cautBinLinieV (start, sfarsit, x - pasi, 0) + cautBinLinieV (start, sfarsit, x - 1, 0);
            x -= pasi;
        }
        if (dir == 'E')
        {
            start = cautBinLinieAux (0, ct, x, 0);
            sfarsit = cautBinLinieAux (0, ct, x, 1);
            rez += -cautBinColoanaAux (start, sfarsit, y + 1, 0) + cautBinColoanaAux(start, sfarsit, y + pasi, 0);
            y += pasi;
        }
        if (dir == 'V')
        {
            start = cautBinLinieAux (0, ct, x, 0);
            sfarsit = cautBinLinieAux (0, ct, x, 1);
            rez += -cautBinColoanaAux (start, sfarsit, y - pasi, 0) + cautBinColoanaAux(start, sfarsit, y - 1, 0);
            y -= pasi;
        }
    }
    fprintf (out, "%d", rez);
    return 0;
}