Cod sursa(job #2378191)

Utilizator fremenFremen fremen Data 11 martie 2019 20:23:20
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

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

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

double det(pair<double, double> x, pair<double, double> y, pair<double, double> z) {
    return x.first * y.second + y.first * z.second + z.first * x.second - y.second * z.first - z.second * x.first - x.second * y.first;
}

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

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

    s[++sol] = v[1];
    s[++sol] = v[2];

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

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

    fout.close();
    return 0;
}