Cod sursa(job #803604)

Utilizator Teodor94Teodor Plop Teodor94 Data 27 octombrie 2012 21:42:46
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <cstdio>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> point;

const int N = 1400000;

int n, m, nrt, nr, xc, yc, nextx, nexty;
point v[N], p[N];

void make_points(point a) {
    v[++nrt].x = a.x - 2;
    v[nrt].y = a.y;

    v[++nrt].x = a.x + 2;
    v[nrt].y = a.y;

    for (int i = a.y - 1; i <= a.y + 1; ++i) {
        v[++nrt].x = a.x - 1;
        v[nrt].y = i;

        v[++nrt].x = a.x + 1;
        v[nrt].y = i;
    }

    for (int i = a.y - 2; i <= a.y + 2; ++i) {
        v[++nrt].x = a.x;
        v[nrt].y = i;
    }
}

void read() {
    scanf("%d%d\n", &n, &m);

    for (int i = 1; i <= n; ++i)
        scanf("%d%d\n", &v[i].x, &v[i].y);
    
    nrt = n;
    for (int i = 1; i <= n; ++i)
        make_points(v[i]);
}

void duplicates() {
    sort(v + 1, v + nrt + 1);

    for (int i = 1; i <= nrt; ++i) {
        p[++nr] = v[i];

        while (v[i] == v[i + 1] && i < nrt)
            ++i;
    }
}

int begin_binary_search(int number, bool type, int start, int fin) {
    int i, pas = 1 << 21;

    for (i = start; pas; pas >>= 1)
        if (i + pas <= fin && type && p[i + pas].y < number)
            i += pas;
        else
        if (i + pas <= fin && !type && p[i + pas].x < number)
            i += pas;

    return i + 1;
}

int end_binary_search(int number, bool type, int start, int fin) {
    int i, pas = 1 << 21;

    for (i = start; pas; pas >>= 1)
        if (i + pas <= fin && type && p[i + pas].y <= number)
            i += pas;
        else
        if (i + pas <= fin && !type && p[i + pas].x <= number)
            i += pas;

    return i;
}

int search(char dir, int lg) {
    int plusx = 0, plusy = 0;
    if (dir == 'N')
        plusy = 1;
    else
    if (dir == 'S')
        plusy = -1;
    else
    if (dir == 'E')
        plusx = 1;
    else
        plusx = -1;

    nextx = xc + plusx * lg;
    nexty = yc + plusy * lg;

    int begin, end, left, right;

    if (plusx) {
        begin = begin_binary_search(yc, true, 0, nr);
        end = end_binary_search(yc, true, 0, nr);

        if (p[begin].y != yc || p[end].y != yc)
            return 0;

        left = begin_binary_search(xc, false, begin - 1, end);
        right = end_binary_search(nextx, false, begin - 1, end);

        return right - left + 1;
    }

    begin = begin_binary_search(xc, false, 0, nr);
    end = end_binary_search(xc, false, 0, nr);

    if (p[begin].x != xc || p[end].x != xc)
        return 0;

    left = begin_binary_search(yc, true, begin - 1, end); 
    right = end_binary_search(nexty, true, begin - 1, end);

    return right - left + 1;
}

void solve() {
    int total = 0;

    for (int i = 1; i <= m; ++i) {
        char dir;
        int lg;
        scanf("%c %d\n", &dir, &lg);

        total += search(dir, lg);
        
        xc = nextx;
        yc = nexty;
    }

    printf("%d\n", total);
}

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

    read();

    duplicates();

    solve();

    return 0;
}