Cod sursa(job #1019611)

Utilizator deneoAdrian Craciun deneo Data 31 octombrie 2013 17:32:42
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("zc.in");
ofstream fout("zc.out");

vector < pair<int, int> > vx, vy;
int n, m;

int abs (int a) {
    if (a < 0)
        return -a;
    return a;
}

void insert_vector (int x, int y) {
    for (int i = -2; i <= 2; ++i)
        for (int j = -2; j <= 2; ++j) {
            if (abs(i) + abs(j) > 2) continue;
            vx.push_back(make_pair(x + i, y + j));
            vy.push_back(make_pair(y + j, x + i));
    }
}

void delete_duplicates (vector< pair<int, int> > &v) {
    int nr = 0;

    for (int i = 1; i < v.size(); ++i) {
        if (v[i] == v[i - 1])
            ++nr;
        else
            v[i - nr] = v[i];
    }

    for (; nr; --nr) v.pop_back();
}

int main() {
    fin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        int x, y;
        fin >> x >> y;

        insert_vector(x, y);
    }

    sort (vx.begin(), vx.end()); delete_duplicates(vx);
    sort (vy.begin(), vy.end()); delete_duplicates(vy);

    int x = 0, y = 0, cost = 0, x1, y1;

    auto it1 = vx.begin(), it2 = vx.begin();

    for (int i = 1; i <= m; ++i) {
        char type; int dist;
        fin >> type >> dist;

        switch (type) {
            case 'E':
                x1 = x + dist; y1 = y;
                it1 = upper_bound(vy.begin(), vy.end(), make_pair(y, x));
                it2 = upper_bound(vy.begin(), vy.end(), make_pair(y, x1));
                break;
            case 'V':
                x1 = x - dist; y1 = y;
                it1 = upper_bound(vy.begin(), vy.end(), make_pair(y, x));
                it2 = upper_bound(vy.begin(), vy.end(), make_pair(y1, x1));
                break;
            case 'S':
                x1 = x; y1 = y - dist;
                it1 = upper_bound(vx.begin(), vx.end(), make_pair(x, y));
                it2 = upper_bound(vx.begin(), vx.end(), make_pair(x1, y1));
                break;
            case 'N':
                x1 = x; y1 = y + dist;
                it1 = upper_bound(vx.begin(), vx.end(), make_pair(x, y));
                it2 = upper_bound(vx.begin(), vx.end(), make_pair(x1, y1));
                break;
        }

        cost += it2 - it1;
        x = x1; y = y1;
    }

    fout << cost;
    return 0;
}