Cod sursa(job #979927)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 3 august 2013 15:03:18
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <algorithm>
#include <stack>
#define x first
#define y second
using namespace std;

typedef pair <double, double> point;
const int NMAX = 120003;
point V[NMAX], S[NMAX];

double cross_product (const point &o, const point &a, const point &b) {

    return (b.x - o.x) * (a.y - o.y) - (b.y - o.y) * (a.x - o.x);

}

bool comp (const point &a, const point &b) {

    return cross_product (V[1], a, b) < 0;

}

int main () {

    freopen ("infasuratoare.in", "r", stdin);
    freopen ("infasuratoare.out", "w", stdout);
    int N, i, m = 1, b;
    scanf ("%d", &N);
    for (i = 1; i <= N; ++i) {
        scanf ("%lf%lf", &V[i].x, &V[i].y);
        if (V[m] > V[i])
            m = i;
    }
    swap (V[1], V[m]);
    sort (V + 2, V + N + 1, comp);
    S[1] = V[1];
    S[2] = V[2];
    b = 2;
    for (i = 3; i <= N; ++i) {
        while (cross_product (V[i], S[b - 1], S[b]) > 0 && b >= 2)
            --b;
        S[++b] = V[i];
    }
    printf ("%d\n", b);
    for (i = 1; i <= b; ++i)
        printf ("%.6lf %.6lf\n", S[i].x, S[i].y);

}