Cod sursa(job #803636)

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> point;

const int N = 1400000;
const int INF = 0x7fffffff;

int n, m, nr, xc, yc, nextx, nexty;
vector<point> v, p;

void make_points(int a, int b) {
    for (int i = a - 2; i <= a + 2; ++i)
        for (int j = b - 2; j <= b + 2; ++j)
            if (abs(i - a) + abs(j - b) <= 2 && i != 0 && j != 0) {
                v.push_back(make_pair(i, j));
                p.push_back(make_pair(j, i));
            }
}

void read() {
    v.push_back(make_pair(-INF, -INF));
    p.push_back(make_pair(-INF, -INF));

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

    for (int i = 1; i <= n; ++i) {
        int a, b;
        scanf("%d%d\n", &a, &b);

        make_points(a, b);
    }
}

void duplicates() {
    sort(v.begin(), v.end());
    sort(p.begin(), p.end());

    int nr = v.size(), nrv = 0, nrp = 0, erase = 1;

    for (int i = 1; i < nr; ++i) {
        if (v[i] != v[i - 1])
            v[++nrv] = v[i];

        if (p[i] != p[i - 1]) {
            p[++nrp] = p[i];

            ++erase;
        }
    }

    erase = nr - erase;

    for (int i = 1; i <= erase; ++i) {
        v.pop_back();
        p.pop_back();
    }
}

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

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

    return i + 1;
}

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

    for (i = start; pas; pas >>= 1)
        if (i + pas <= fin && type && a[i + pas].y <= number)
            i += pas;
        else
        if (i + pas <= fin && !type && a[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, p);
        end = end_binary_search(yc, true, 0, nr, p);

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

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

        return right - left + 1;
    }

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

    if (v[begin].x != xc)
        return 0;

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

    return right - left + 1;
}

void solve() {
    nr = v.size();
    
    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;
}