Cod sursa(job #657778)

Utilizator Teodor94Teodor Plop Teodor94 Data 7 ianuarie 2012 13:31:17
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<cstdio>
#include<algorithm>

using namespace std;

const int INF = 1000000000;

const int N = 120002;

int n, first, pos[N], st[N];
double x[N], y[N];

void citire() {
    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lf %lf", &x[i], &y[i]);
}

void init() {
    x[0] = INF, y[0] = INF;
    int first = 0;

    for (int i = 1; i <= n; ++i)
        if (x[i] < x[first] || (x[i] == x[first] && y[i] < y[first]))
            first = i;

    for (int i = 1; i <= n; ++i) {
        if (i == first)
            continue;
        pos[++pos[0]] = i;
    }
}

bool comp(int i, int j) {
    return (double) (x[i] - x[first]) * (y[j] - y[first]) < (double) (x[j] - x[first]) * (y[i] - y[first]);
}

long double panta(int i, int j, int k) {
    return (long double) x[i] * y[j] + x[j] * y[k] + x[k] * y[i] - y[i] * x[j] - y[j] * x[k] - y[k] * x[i];
}

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

    citire();

    init();

    sort(pos + 1, pos + pos[0] + 1, comp);

    st[0] = 1;
    st[1] = first;

    for (int i = 1; i <= pos[0]; ++i) {
        if (pos[i] == first)
            continue;
        while (st[0] >= 2 && panta(st[st[0] - 1], st[st[0]], pos[i]) > 0)
            --st[0];
        st[++st[0]] = pos[i];
    }

    st[++st[0]] = first;

    printf("%d\n", st[0] - 1);

    reverse(st + 1, st + st[0] + 1);

    for (int i = 1; i < st[0]; ++i)
        printf("%lf %lf\n", x[st[i]], y[st[i]]);

    return 0;
}