Cod sursa(job #657792)

Utilizator Teodor94Teodor Plop Teodor94 Data 7 ianuarie 2012 14:00:16
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 120002;
const double INF = 1000000000;

int n, nn = 2, poz;

struct punct {
    double x, y, p;
};

punct a[N], s[N], z;

void citire() {
    z.x = z.y = INF;

    scanf("%d ", &n);

    for (int i = 0; i < n; ++i) {
        scanf("%lf %lf ", &a[i].x, &a[i].y);

        if (a[i].x < z.x || (a[i].x == z.x && a[i].y < z.y)) {
            z.x = a[i].x;
            z.y = a[i].y;
            poz = i;
        }
    }

    a[poz] = a[n - 1];
    --n;
}

void panta() {
    for (int i = 0; i < n; ++i)
        if (a[i].x == z.x)
            a[i].p = INF;
        else
            a[i].p = (a[i].y - z.y) / (a[i].x - z.x);
}

bool comp(punct a, punct b) {
    if (a.p > b.p)
        return false;
    return true;
}

bool determinant(punct a, punct b, punct c) {
    double det = (double) a.x * b.y + a.y * c.x + b.x * c.y - a.y * b.x - b.y * c.x - c.y * a.x;
    if (det >= 0)
        return 1;
    return 0;
}

void infasuratoare() {
    s[0] = z;
    s[1] = a[0];
    for (int i = 1; i < n; ++i)
        if (determinant(s[nn - 2], s[nn - 1], a[i]) == 1)
            s[nn++] = a[i];
        else {
            while (determinant(s[nn - 2], s[nn - 1], a[1]) == 0)
                s[--nn] = a[i];
            ++nn;
        }
}

void afisare() {
    printf("%d\n", nn);
    for (int i = 0; i < nn; ++i)
        printf("%lf %lf\n", s[i].x, s[i].y);
}

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

    citire();

    panta();

    sort(a, a + n, comp);

    infasuratoare();

    afisare();

    return 0;
}