Cod sursa(job #2539709)

Utilizator theo2003Theodor Negrescu theo2003 Data 6 februarie 2020 10:37:44
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
pair<long double, long double> points[120000];
int main() {
    ios_base::sync_with_stdio(0);
    cin>>n;
    for(int x = 0; x<n; x++)
        cin>>points[x].first>>points[x].second;
    for(int x = 1; x<n; x++) {
        if(points[x] < points[0])
            swap(points[0], points[x]);
    }
    {
        auto first = points[0];
        sort(points + 1, points + n, [first](pair<long double, long double> a, pair<long double, long double> b) {
            return (a.first - points[0].first)*(b.second - points[0].first) < (b.first - points[0].first)*(a.second - points[0].first);
        });
    }
    vector<pair<long double, long double> > hull = {points[0], points[1]};
    hull.reserve(n);
    for(int x = 2;x<n;x++){
        while((hull.size() > 2) && (0 < ((hull.back().first - hull[hull.size() - 2].first)*(points[x].second - hull[hull.size() - 2].second) - (hull.back().second - hull[hull.size() - 2].second)*(hull.back().first - hull[hull.size() - 2].first)))){
            hull.pop_back();
        }
        hull.push_back(points[x]);
    }
    cout<<setprecision(20)<<hull.size()<<'\n';
    for(auto p : hull)
        cout<<p.first<<' '<<p.second<<'\n';
    return 0;
}