Cod sursa(job #3350282)

Utilizator pkseVlad Bondoc pkse Data 6 aprilie 2026 22:04:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
#define fi first 
#define se second 
#define pb emplace_back
#define double double long 
using namespace std;

double d(pair<double, double> a, pair<double, double> b) {
    return a.fi * b.se - a.se * b.fi;
}

double orient(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
    return d(a, b) + d(b, c) + d(c, a);
}



int main() {
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;

    int mn = 0;

    vector<pair<double, double>> a(n);

    for(int i = 0; i < n; i ++) {
        cin >> a[i].fi >> a[i].se;
        if(a[mn] > a[i]) {
            mn = i;
        }
    }

    swap(a[mn], a[0]);

    sort(a.begin() + 1, a.end(), [&](pair<double, double> i, pair<double, double> j) {
        return orient(a[0], i, j) < 0;
    });

    vector<pair<double, double>> stk;
    stk.pb(a[0]);
    stk.pb(a[1]);   

    for(int i = 2; i < n; i ++) {
        while(stk.size() > 1 && orient(stk[stk.size() - 2], stk[stk.size() - 1], a[i]) > 0) {
            stk.pop_back();
        }
        stk.push_back(a[i]);
    }

    cout << stk.size() << '\n';
    reverse(stk.begin(), stk.end());

    for(auto &[i, j] : stk) {
        cout << fixed << setprecision(6) << i << ' ' << j << '\n';
    }
}