Cod sursa(job #1906865)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 6 martie 2017 16:44:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

#define point pair < double, double >
#define x first
#define y second

using namespace std;

const int nmax = 12e4 + 10;

int n;
int last, v[nmax];
point p[nmax];

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

double det(point a, point b, point c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

bool sgn(int a, int b, int c) {
    return det(p[a], p[b], p[c]) < 0.0;
}

void run_convexHull() {
    sort(p + 1, p + n + 1);

    v[++last] = 1;
    for (int i = 2; i <= n; ++i) {
        while (last > 1 && sgn(v[last-1], v[last], i))
            last--;
        v[++last] = i;
    }

    for (int i = n - 1; i; --i) {
        while (last > 1 && sgn(v[last-1], v[last], i))
            last--;
        v[++last] = i;
    }

    last--;
}

void output() {
    printf("%d\n", last);
    for (int i = 1; i <= last; ++i)
        printf("%.10f %.10f\n", p[v[i]].x, p[v[i]].y);
}

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

    input();
    run_convexHull();
    output();

    return 0;
}