Cod sursa(job #500937)

Utilizator cont_de_testeCont Teste cont_de_teste Data 13 noiembrie 2010 19:36:51
Problema Zota & Chidil Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
# include <algorithm>
# include <cstdio>
# include <vector>
using namespace std ;

# define x 	         first
# define y 	         second
# define pb          push_back
# define mp          make_pair
# define sr(V, val)  V.begin (), V.end (), val
# define ub          upper_bound
# define lb          lower_bound

typedef pair < int, int > PR ;
const char *FIN = "zc.in", *FOU = "zc.out" ;
const int di[] = { -2, -1, -1, -1,  0,  0, 0, 0, 0,  1, 1, 1, 2 } ;
const int dj[] = {  0, -1,  0,  1, -2, -1, 0, 1, 2, -1, 0, 1, 0 } ;
const int MAX = 100005 ;

PR A[MAX], now, next;
vector < PR > X, Y;
int N, M, Nxy, Sol;

void baga_marfa ( int x, int y ) {
    for ( int i = 0; i <= 12; ++i ) {
        if ( x + di[i] || y + dj[i] ) {
            X.pb ( mp ( x + di[i], y + dj[i] ) ) ;
            Y.pb ( mp ( y + dj[i], x + di[i] ) ) ;
        }
    }
}

void do_it ( char c, int val ) {
    next = now;

    if (c == 'N') {
        next.y += val ;
        Sol += ( abs ( ub ( sr ( X, next ) ) - ub ( sr ( X, now ) ) ) ) ;
    } else if (c == 'S') {
        next.y -= val ;
        Sol += abs ( lb ( sr ( X, now ) ) - lb ( sr ( X, next ) ) ) ;
    } else if (c == 'V') {
        next.x -= val ;
        Sol += abs ( lb ( sr ( X, mp ( now.y, now.x ) ) ) - lb ( sr ( X, mp ( next.y, next.x ) ) ) ) ;
    } else {
        next.x += val ;
        Sol += abs ( ub ( sr ( X, mp ( next.y, next.x ) ) ) - ub ( sr ( X, mp ( now.y, now.x ) ) ) ) ;
    }
    now = next;
}
int main () {
    int i, val;
    vector < PR > :: iterator it;
    char c;

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

    scanf("%d%d", &N, &M);

    for (i = 1; i <= N; ++ i) {
        scanf("%d%d", &A[i].x, &A[i].y);
        baga_marfa ( A[i].x, A[i].y ) ;
    }

    sort (X.begin(), X.end());
    X.resize(unique(X.begin(), X.end()) - X.begin());

    sort (Y.begin(), Y.end());
    Y.resize(unique(Y.begin(), Y.end()) - Y.begin());

    for (; M -- ;) {
        scanf(" %c %d", &c, &val);
        do_it (c, val);
    }

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