Cod sursa(job #2531876)

Utilizator flibiaVisanu Cristian flibia Data 26 ianuarie 2020 20:27:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
#define ld long double
#define fi first
#define se second

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

int n, vf;
pair<ld, ld> pts[120100];

int main() {
    auto delta = [&](pair<ld, ld> a, pair<ld, ld> b, pair<ld, ld> c) {
        return a.fi * b.se + b.fi * c.se + c.fi * a.se - a.se * b.fi - b.se * c.fi - c.se * a.fi;
    };

    in >> n;
    for (int i = 1; i <= n; i++)    
        in >> pts[i].fi >> pts[i].se;

    sort(pts + 1, pts + n + 1);
    sort(pts + 2, pts + n + 1, [&](pair<ld, ld> a, pair<ld, ld> b) {
        return delta(pts[1], a, b) < 0;
    });

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

    out << vf << '\n';
    for (; vf > 0; vf--)
        out << fixed << setprecision(6) << pts[vf].fi << ' ' << pts[vf].se << '\n';

    return 0;
}