Cod sursa(job #2980589)

Utilizator DordeDorde Matei Dorde Data 16 februarie 2023 17:47:21
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <algorithm>
#include <fstream>
#include <iomanip>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int const N = 120001;
int n;
int st[N] , l[N] , r[N] , idx[N] , ans[N];
double  X[N] , Y[N];
double area(int i , int j , int k){
    return X[i] * (Y[j] - Y[k]) + X[j] * (Y[k] - Y[i]) + X[k] * (Y[i] - Y[j]);
}
int main(){
    fin >> n;
    for(int i = 1 ; i <= n ; ++ i){
        fin >> X[i] >> Y[i];
        idx[i] = i;
    }
    sort(idx + 1 , idx + 1 + n);
    int vf;
    st[vf = 1] = idx[1];
    for(int j = 2 ; j <= n ; ++ j){
        int i = idx[j];
        while(vf > 1 && area(st[vf - 1] , st[vf] , i) < 0){
            --vf;
        }
        st[++vf] = i;
    }
    for(int i = 1 ; i <= vf ; ++ i)
        ans[i] = st[i];
    ans[0] = vf;
    st[vf = 1] = idx[1];
    for(int j = 2 ; j <= n ; ++ j){
        int i = idx[j];
        while(vf > 1 && area(st[vf - 1] , st[vf] , i) > 0){
            --vf;
        }
        st[++vf] = i;
    }
    for(int i = vf - 1 ; i > 1 ; -- i)
        ans[++ans[0]] = st[i];
    fout << ans[0] << '\n';
    for(int i = 1 ; i <= ans[0] ; ++ i){
        fout << fixed << setprecision(12);
        fout << X[ans[i]] << ' ' << Y[ans[i]] << '\n';
    }
    return 0;
}