Cod sursa(job #500946)

Utilizator SpiderManSimoiu Robert SpiderMan Data 13 noiembrie 2010 20:05:22
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 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 be(V)       V.begin (), V.end ()
# define sr(V, x)  be(V), x
# 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 act, rec, V[MAX] ;
vector < PR > VX, VY ;
int N, M, rez, x ;
char D ;

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

void rezve ( char D, int x ) {
    act = rec ;
    switch ( D ) {
    case 'E' :
        act.x += x ;
        rez += abs ( ub ( sr ( VY, mp ( act.y, act.x ) ) ) - ub ( sr ( VY, mp ( rec.y, rec.x ) ) ) ) ;
        break ;
    case 'V' :
        act.x -= x ;
        rez += abs ( lb ( sr ( VY, mp ( rec.y, rec.x ) ) ) - lb ( sr ( VY, mp ( act.y, act.x ) ) ) ) ;
        break ;
    case 'N' :
        act.y += x ;
        rez += ( abs ( ub ( sr ( VX, act ) ) - ub ( sr ( VX, rec ) ) ) ) ;
        break ;
    case 'S' :
        act.y -= x ;
        rez += abs ( lb ( sr ( VX, rec ) ) - lb ( sr ( VX, act ) ) ) ;
        break ;
    }
    rec = act ;
}

int main ( void ) {
    freopen ( FIN, "r", stdin ) ;

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

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

    sort ( be ( VX ) ) ;
    VX.resize ( unique ( be ( VX ) ) - VX.begin () ) ;

    sort ( be ( VY ) ) ;
    VY.resize ( unique ( be ( VY ) ) - VY.begin () ) ;

    for ( ; M ; --M ) {
        scanf ( " %c %d", &D, &x ) ;
        rezve ( D, x ) ;
    }

    fprintf ( fopen ( FOU, "w" ) , "%d", rez ) ;
}