Cod sursa(job #800879)

Utilizator Teodor94Teodor Plop Teodor94 Data 22 octombrie 2012 20:42:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>

#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<double, double> Point;

const int N = 120005;

int n, nr;
Point v[N], stack[N];

void read() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf", &v[i].x, &v[i].y);
}

inline double cross_product(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline bool cmp(const Point& p1, const Point& p2) {
    return cross_product(v[1], p1, p2) < 0;
}

void set_points() {
    int pos = 1;

    for (int i = 2; i <= n; ++i)
        if (v[i] < v[pos])
            pos = i;

    swap(v[1], v[pos]);

    sort(v + 2, v + n + 1, cmp);
}

void convex_hull() {
    set_points();

    stack[1] = v[1];
    stack[2] = v[2];

    nr = 2;

    for (int i = 3; i <= n; ++i) {
        while (nr >= 2 && cross_product(stack[nr - 1], stack[nr], v[i]) > 0)
            --nr;

        stack[++nr] = v[i];
    }
}

void write() {
    printf("%d\n", nr);

    for (int i = nr; i > 0; --i)
        printf("%.6lf %.6lf\n", stack[i].x, stack[i].y);
}

int main() {
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out" ,"w", stdout);

    read();

    convex_hull();

    write();

    return 0;
}