Cod sursa(job #1511669)

Utilizator tudoras8tudoras8 tudoras8 Data 26 octombrie 2015 23:54:33
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

#define x first
#define y second

typedef long long ll;

using namespace std;

typedef pair<double, double> point;

const int MAXN = 120000;
ll n;
point pts[MAXN];
int hull[MAXN];

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

    return result;
}

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 >> pts[i].x >> pts[i].y;
    }

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

    hull[0] = 0;
    hull[1] = 1;
    int k = 2;

    for (int i = 2; i < n; ++i) {
        while (k >= 3 && cross_product(pts[hull[k - 2]], pts[hull[k - 1]], pts[i]) > 0) {
            --k;
        }

        hull[k] = i;
        ++k;
    }

    sort(hull, hull + k, [&pts](int ptId1, int ptId2) {
        return (pts[ptId1].x * pts[ptId2].y - pts[ptId1].y * pts[ptId2].x) < 0;
    });

    cout << k << '\n' << setprecision(6) << fixed;
    for (int i = k - 1; i >= 0; --i) {
        cout << pts[hull[i]].x << ' ' << pts[hull[i]].y << '\n';
    }

    return 0;
}