Cod sursa(job #2416706)

Utilizator fremenFremen fremen Data 27 aprilie 2019 22:16:32
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <iomanip>
using namespace std;

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

const int MAXN = 120005;
int n;
pair<double, double> v[MAXN];

double det(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
    return a.first * b.second + b.first * c.second + c.first * a.second - b.second * c.first - c.second * a.first - a.second * b.first;
}

bool srt(pair<double, double> a, pair<double, double> b) {
    return (det(v[1], a, b) > 0);
}

int s;
pair<int, int> sol[MAXN];

int main() {

    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i].first >> v[i].second;
    }

    sort(v + 1, v + n + 1);
    sort(v + 2, v + n + 1, srt);
    sol[++s] = v[1];
    sol[++s] = v[2];

    for (int i = 3; i <= n; ++i) {
        while (s > 2 && det(sol[s - 1], sol[s], v[i]) <= 0) {
            s--;
        }
        sol[++s] = v[i];
    }

    fout << s << '\n';
    fout << fixed << setprecision(6);
    for (int i = 1; i <= s; ++i) {
        fout << sol[i].first << ' ' << sol[i].second << '\n';
    }

    fout.close();
    return 0;
}