Cod sursa(job #2539751)

Utilizator theo2003Theodor Negrescu theo2003 Data 6 februarie 2020 11:30:35
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 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];
inline long double cross(pair<long double, long double> a, pair<long double, long double> b, pair<long double, long double> c){
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin>>n;
    for(int x = 0; x<n; x++)
        cin>>points[x].first>>points[x].second;
    int tmp = 0;
    for(int x = 1;x<n;x++){
        if(points[tmp] > points[x])
            tmp = x;
    }
    swap(points[0], points[tmp]);
    {
        auto first = points[0];
        sort(points + 1, points + n, [first](pair<long double, long double> a, pair<long double, long double> b) {
            return cross(first, a, b) < 0;
        });
    }
    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) && (cross(hull[hull.size() - 2], hull.back(), points[x]) > 0)){
            hull.pop_back();
        }
        hull.push_back(points[x]);
    }
    cout<<setprecision(20)<<hull.size()<<'\n';
    for(auto p = hull.rbegin();p!=hull.rend();p++)
        cout<<p->first<<' '<<p->second<<'\n';
    return 0;
}