Cod sursa(job #903098)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 1 martie 2013 18:31:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <cstring>
#include <cassert>

#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef vector<int>::iterator it;
typedef pair<double, double> Point;

const int oo = 0x3f3f3f3f;
const int MAX_N = 120005;
const double Eps = 1e-12;

int N, Hull[MAX_N];
Point P[MAX_N];
bool Used[MAX_N];

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

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

void Solve() {
    ConvexHull();
}

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", Hull[0] - 1);
    for (int i = 1; i < Hull[0]; ++i)
        printf("%.8lf %.8lf\n", P[Hull[i]].x, P[Hull[i]].y);
}

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