Cod sursa(job #2247752)

Utilizator pinteastefanPintea Teodor Stefan pinteastefan Data 29 septembrie 2018 00:15:02
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;

vector < pair <long double , long double > > puncte;
vector < pair <long double , long double >> stivaPuncte;

long double determinant(pair <long double, long double> penultimul, pair <long double, long double> ultimul, pair < long double, long double> actual){
    long double rezultat;
    rezultat = penultimul.first * ultimul.second + ultimul.first * actual.second + actual.first * penultimul.second -
            ultimul.second * actual.first - actual.second * penultimul.first - penultimul.second * ultimul.first;
    return rezultat;
}

int main() {
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int n;
    pair <long double, long double> minim = make_pair(1e9 + 1, 1e9 + 1);
    f >> n;
    for (int i = 1; i <=n; i ++){
        long double x, y;
        f >> x >> y;
        puncte.emplace_back(x,y);
        minim = min (minim, make_pair(x, y));
    }

    sort(puncte.begin(), puncte.end(), [&](auto &a, auto &b) {
        return determinant(minim, a, b) < 0;
    });

    stivaPuncte.push_back(puncte[0]);
    stivaPuncte.push_back(puncte[1]);
    for (int i = 2; i < (int)puncte.size(); ++ i){
        auto x = puncte[i];
        while (stivaPuncte.size() > 1 and determinant(stivaPuncte[(int)stivaPuncte.size() - 2], stivaPuncte.back(), x) > 0){
            stivaPuncte.pop_back();
        }
        stivaPuncte.push_back(x);
    }
    reverse(stivaPuncte.begin(), stivaPuncte.end());
    g << stivaPuncte.size() << '\n';
    for (auto x : stivaPuncte){
        g << fixed << setprecision(7) << x.first << ' ' << x.second << "\n" ;
    }
    return 0;
}