Cod sursa(job #979947)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 3 august 2013 16:33:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <algorithm>
#include <bitset>
#define x first
#define y second
using namespace std;

const int NMAX = 120003;
typedef pair <double, double> point;

bitset <NMAX> viz;
point P[NMAX];
int S[NMAX];

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

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

}

int main () {

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

    int N, i, b, k = 1;
    scanf ("%d", &N);
    for (i = 1; i <= N; ++i)
        scanf ("%lf%lf", &P[i].x, &P[i].y);
    sort (P + 1, P + N + 1);
    S[1] = 1;
    S[2] = 2;
    b = 2;
    for (i = 3; i >= 1; i += (k = (i == N ? -k : k))) {
        if (viz[i])
            continue;
        while (cross_product (P[i], P[S[b - 1]], P[S[b]]) < 0 && b >= 2)
            viz[S[b--]] = 0;
        S[++b] = i;
        viz[i] = 1;
    }
    printf ("%d\n", b - 1);
    for (i = 1; i < b; ++i)
        printf ("%.6lf %.6lf\n", P[S[i]].x, P[S[i]].y);

}