Cod sursa(job #812669)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 14 noiembrie 2012 10:40:20
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <algorithm>
#include <cassert>

#define x first
#define y second

using namespace std;

typedef pair<double, double> Point;

const int MaxN = 125000;
const double Eps = 1e-12;

Point P[MaxN];
int N, Hull[MaxN], K;
bool Used[MaxN];

inline double Angle(Point P1, Point P2, Point P3) {
    return P1.x*P2.y + P2.x*P3.y + P3.x*P1.y - P2.y*P3.x - P3.y*P1.x - P1.y*P2.x;
}

void ConvexHull() {
    sort(P+1, P+N+1);
    Hull[++K] = 1;
    for (int i = 2, p = 1; i > 0; i += (p = (i == N ? -p : p))) {
        if (Used[i])
            continue;
        while (K > 1 && Angle(P[Hull[K-1]], P[Hull[K]], P[i]) <= Eps)
            Used[Hull[K--]] = false;
        Used[Hull[++K] = i] = true;
    }
}

void Read() {
    assert(freopen("infasuratoare.in", "r", stdin));
    assert(scanf("%d", &N) == 1);
    for (int i = 1; i <= N; ++i)
        assert(scanf("%lf %lf", &P[i].x, &P[i].y) == 2);
}

void Print() {
    assert(freopen("infasuratoare.out", "w", stdout));
    printf("%d\n", K-1);
    for (int i = 1; i < K; ++i)
        printf("%.7lf %.7lf\n", P[Hull[i]].x, P[Hull[i]].y);
}

int main() {
    Read();
    ConvexHull();
    Print();
    return 0;
}