Cod sursa(job #1815418)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 25 noiembrie 2016 10:56:46
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <algorithm>
#include <vector>

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

using namespace std;

const int nmax = 1e5 + 10;

int n;
point a[nmax];

vector < int > v;

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

int determinant(point a, point b, point c) {
    return (a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - a.y * b.x - a.x * c.y < 0);
}

int det(int idx1, int idx2, int idx3) {
    return determinant(a[idx1], a[idx2], a[idx3]);
}

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

    v.push_back(1);
    for (int i = 2; i <= n; ++i) {
        while ((int)v.size() > 1 && det(v[(int)v.size()-2],v.back(), i))
            v.pop_back();
        v.push_back(i);
    }

    for (int i = n - 1; i ; --i) {
        while ((int)v.size() > 1 && det(v[(int)v.size()-2],v.back(), i))
            v.pop_back();
        v.push_back(i);
    }

    v.pop_back();
}

void output() {
    printf("%d\n", (int)v.size());
    for (auto &it : v)
        printf("%.12f %.12f\n", a[it].x, a[it].y);
}

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

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

    return 0;
}