Cod sursa(job #2477561)

Utilizator flibiaVisanu Cristian flibia Data 20 octombrie 2019 17:22:42
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define ll long long 
#define fi first
#define se second 
#define ld long double
#define EPS 0.000000000001

using namespace std;

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

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

ld 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);
}

bool cmp(pair<ld, ld> a, pair<ld, ld> b) {
    return delta(conv[1], a, b) + EPS < 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    in >> n;

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

    sort(pts + 1, pts + n + 1);
    conv[++vf] = pts[1];
    sort(pts + 2, pts + n + 1, cmp);
    conv[++vf] = pts[2];

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

    out << vf << '\n';
    while (vf--)
        out << fixed << setprecision(12) << conv[vf + 1].fi << ' ' << conv[vf + 1].se << '\n';

    return 0;
}