Cod sursa(job #1512514)

Utilizator tudoras8tudoras8 tudoras8 Data 28 octombrie 2015 10:18:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

#define x first
#define y second

using namespace std;

typedef pair<double, double> point;

const int MAXN = 120001;

int n, head, stack[MAXN];
point v[MAXN];

double cross_product(const point &O, const point &A, const point &B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#else
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
#endif // LOCAL

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> v[i].x >> v[i].y;
    }

    sort(v + 1, v + n, [&O = v[0]](const point &A, const point &B) {
        return cross_product(O, A, B) < 0;
    });

    stack[0] = 0;
    stack[1] = 1;
    head = 1;
    for (int i = 2; i < n; ++i) {
        if (head + 1 >= 2 && cross_product(v[stack[head - 1]], v[stack[head]], v[i]) >= 0) {
            --head;
        }
        ++head;
        stack[head] = i;
    }

    cout << head + 1 << '\n';
    cout << fixed << setprecision(6);
    for (int i = 0; i <= head; ++i) {
        cout << v[stack[i]].x <<  ' ' << v[stack[i]].y << '\n';
    }

    return 0;
}