Cod sursa(job #1165288)

Utilizator SRaduRadu Szasz SRadu Data 2 aprilie 2014 16:43:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

const int MAX = 120120;
const double EPS = 1e-12;

#define PII pair<double, double>
#define x first
#define y second

int N, head;
int stk[MAX];

bool inStack[MAX];

PII P[MAX];

void citire() {
    ifstream in("infasuratoare.in");
    in >> N;
    for(int i = 1; i <= N; i++) {
        in >> P[i].x >> P[i].y;
    } in.close();
}

double crossProduct(PII O, PII A, PII B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

void solve() {
    sort(P + 1, P + N + 1); 

    stk[1] = 1;
    stk[2] = 2;
    inStack[2] = true;
    head = 2;
    for(int i = 1, p = 1; i; i += (p = (i == N ? -p : p))) {
        if(inStack[i]) continue;
        while(head >= 2 && crossProduct(P[ stk[head - 1] ], P[ stk[head] ], P[i]) < EPS) {
            inStack[ stk[head--] ] = false;
        }
        stk[++head] = i;
        inStack[i] = true;
    }
}

void afisare() {
    ofstream out("infasuratoare.out");
    out << head - 1 << "\n";
    for(int i = 1; i < head; i++) {
        out << fixed << setprecision(6) << P[ stk[i] ].x << " " << P[ stk[i] ].y << "\n";
    } out.close();
}

int main() {
    citire();
    solve();
    afisare();
}