Cod sursa(job #2980747)

Utilizator DordeDorde Matei Dorde Data 16 februarie 2023 19:42:55
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int const N = 120001;
double const prec = 1e-12;
int 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]);
}
bool crt(int i , int j){
    if(X[i] == X[j])
        return Y[i] < Y[j];
    return X[i] < X[j];
}
int idx[N];
int st[N] , dr[N];
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 , crt);
    dr[dr[0] = 1] = idx[1];
    for(int i = 2 ; i <= n ; ++ i){
        while(dr[0] > 1 && area(dr[dr[0] - 1] , dr[dr[0]] , idx[i]) < 0)
            --dr[0];
        dr[++dr[0]] = idx[i];
    }
    st[st[0] = 1] = idx[1];
    for(int i = 2 ; i <= n ; ++ i){
        while(st[0] > 1 && area(st[st[0] - 1] , st[st[0]] , idx[i]) > 0)
            --st[0];
        st[++st[0]] = idx[i];
    }
    fout << st[0] + dr[0] - 2 << '\n';
    for(int i = 1 ; i <= dr[0] ; ++ i)
        fout << fixed << setprecision(12) << X[dr[i]] << ' ' << Y[dr[i]] << '\n';
    for(int i = st[0] - 1 ; i > 1 ; -- i)
        fout << fixed << setprecision(12) << X[st[i]] << ' ' << Y[st[i]] << '\n';
    return 0;
}