Cod sursa(job #500952)

Utilizator SpiderManSimoiu Robert SpiderMan Data 13 noiembrie 2010 20:33:13
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
# include <algorithm>
# include <cstdio>
# include <vector>
using namespace std ;

# define verf        ++poz == hg ? fread ( ch, 1, hg, stdin ), poz = 0 : 0
# define ck(x)       ( x == 'N' || x == 'S' || x == 'E' || x == 'V' )
# 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, hg = 1 << 13 ;

PR act, rec ;
vector < PR > VX, VY ;
int N, M, rez, x, poz, D ;
char ch[ hg ] ;

inline void cit ( int &x ) {
    if ( ch[0] == '\0' ) fread ( ch, 1, hg, stdin ) ;
    else for ( ; ( ch[poz] < '0' || ch[poz] > '9' ) && ! ck ( ch[poz] ) ; verf ) ;
    for ( x = 0 ; ch[poz] >= '0' && ch[poz] <= '9' || ck ( ch[poz] ) ; x = x * 10 + ch[poz] - '0', verf ) ;
}

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 solve ( int D, int x ) {
    act = rec ;
    switch ( D ) { // cercetam directia
    case 21 :
        act.x += x ;
        rez += abs ( ub ( sr ( VY, mp ( act.y, act.x ) ) ) - ub ( sr ( VY, mp ( rec.y, rec.x ) ) ) ) ;
        break ;
    case 38 :
        act.x -= x ;
        rez += abs ( lb ( sr ( VY, mp ( rec.y, rec.x ) ) ) - lb ( sr ( VY, mp ( act.y, act.x ) ) ) ) ;
        break ;
    case 30 :
        act.y += x ;
        rez += abs ( ub ( sr ( VX, act ) ) - ub ( sr ( VX, rec ) ) ) ;
        break ;
    case 35 :
        act.y -= x ;
        rez += abs ( lb ( sr ( VX, rec ) ) - lb ( sr ( VX, act ) ) ) ;
        break ;
    }
    rec = act ;
}

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

    cit ( N ) , cit ( M ) ;
    for ( int i = 1, xx, yy; i <= N; ++i ) {
        cit ( xx ) , cit ( yy ) ;
        mk_Vec ( xx, yy ) ;
    }

    sort ( be ( VX ) ) ; // primul vector
    VX.resize ( unique ( be ( VX ) ) - VX.begin () ) ;

    sort ( be ( VY ) ) ; // al doilea vector
    VY.resize ( unique ( be ( VY ) ) - VY.begin () ) ;

    for ( ; M ; --M ) {
        cit ( D ) , cit ( x ) ;
        solve ( D, x ) ;
    }

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