Cod sursa(job #600047)

Utilizator SpiderManSimoiu Robert SpiderMan Data 30 iunie 2011 13:50:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
# include <algorithm>
# include <fstream>
# include <deque>
# include <iomanip>
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;
const db EPS = 1e-12;

ifstream f (FIN);
ofstream g (FOU);

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

int N;
PR V[MAX];

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 ());
    }
    g << stk.size () - 1 << "\n";
    g << setprecision (6) << fixed;
    for (size_t i = 0, j = stk.size () - 1; i < j; ++i)
        g << V[stk[i]].x << " " << V[stk[i]].y << "\n";
}

int main (void) {
    f >> N;
    for (int i = 1; i <= N; ++i)
        f >> V[i].x >> V[i].y;
    convexhull ();
}