Cod sursa(job #600033)

Utilizator cont_de_testeCont Teste cont_de_teste Data 30 iunie 2011 13:29:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
# include <algorithm>
# include <bitset>
# 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;
const db EPS = 1e-12;

# define x first
# define y second

int N;
PR V[MAX];

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

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

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;
int viz[MAX];

void convexhull (void) {
    int wh = 1;
    # define pb push_back
    # define Pb pop_back
    sort (V + 1, V + N + 1, comp);
    stk.pb (1), stk.pb (2), viz[2] = 1;
    for (int i = 3; viz[1] == 0; stk.pb (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.Pb ());
    }
    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);
    for (int i = 1; i <= N; ++i)
        scanf ("%lf %lf", &V[i].x, &V[i].y);
    convexhull ();
}