Cod sursa(job #600049)

Utilizator SpiderManSimoiu Robert SpiderMan Data 30 iunie 2011 14:04:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
# include <algorithm>
# include <cstdio>
# include <deque>
using namespace std;

typedef double db;
typedef pair <db, db> PR;
const char *FIN = "infasuratoare.in", *FOU = "infasuratoare.out";
const int MAX = 120005, hg = 1 << 13, f[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
const db EPS = 1e-12;

# define verf ++poz == hg ? fread ( ch, 1, hg, stdin ), poz = 0 : 0
# define x first
# define y second

int N, poz;
PR V[MAX];

char ch[ hg ] ;

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

inline int check (db A, db B) {
    if (B - A > EPS) return -1;
    if (A - B > EPS) return  1;
    return 0;
}

bool comp (const PR &A, const PR &B) {
    int X = check (A.x, B.x);
    if (X) return X < 0;
    return check (A.y, B.y) < 0;
}

inline int in (PR A, PR B, PR C) {
    return check ((A.y - B.y) * C.x + (B.x - A.x) * C.y + (A.x * B.y) - (B.x * A.y), 0);
}

deque <int> stk;
bool viz[MAX];

void convexhull (void) {
    int wh = 1;
    sort (V + 1, V + N + 1, comp);
    stk.push_back (1), stk.push_back (2), viz[2] = 1;
    for (int i = 3; viz[1] == 0; stk.push_back (i), viz[i] = 1) {
        for (; viz[i] ; i += wh = (i == N ? -1 : wh)) ;
        for (; stk.size () > 1 && in (V[*(stk.end () - 2)], V[stk.back ()], V[i]) < 0; viz[stk.back ()] = 0, stk.pop_back ());
    }
    printf ("%d\n", stk.size () - 1);
    for (size_t i = 0, j = stk.size () - 1; i < j; ++i)
        printf ("%.6lf %.6lf\n", V[stk[i]].x, V[stk[i]].y);
}

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

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