Cod sursa(job #3297351)

Utilizator Arhiva_EducationalaArhiva Educationala Arhiva_Educationala Data 22 mai 2025 14:58:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 120'000;
const double EPS = 0.001;

complex <double> v[NMAX + 1];

bool isZero( double a ) {
    return abs( a ) <= EPS;
}
bool eq( double a, double b ) {
    return isZero( a - b );
}
double cross( complex<double> a, complex<double> b ) {
    return a.real() * b.imag() - a.imag() * b.real();
}
double det( complex<double> a, complex<double> b, complex<double> c ) {
    return cross( b - a, c - a );
}
int main() {
    ifstream fin( "infasuratoare.in" );
    ofstream fout( "infasuratoare.out" );
    int n;
    fin >> n;
    for ( int i = 0; i < n; i ++ ) {
        double x, y;
        fin >> x >> y;
        v[i] = {x, y};
    }
    sort( v, v + n, []( complex <double> a, complex <double> b ) {
        if ( a.real() != b.real() ) return a.real() <= b.real();
        return a.imag() <= b.imag();
    } );
    sort( v + 1, v + n, [&]( complex <double> a, complex <double> b ) {
        a -= v[0];
        b -= v[0];
        double aux1 = a.imag() * b.real(), aux2 = b.imag() * a.real();
        
        if ( eq( aux1, aux2 ) ) {
            if ( !eq( a.real(), b.real() ) ) return a.real() <= b.real();
            return a.imag() <= b.imag();
        }
        return aux1 < aux2;
    } );

    deque <complex<double>> st;

    for ( int i = 0; i < n; i ++ ) {
        while ( st.size() >= 2 && det( st[st.size() - 2], st[st.size() - 1], v[i] ) < 0 ) st.pop_back();
        st.push_back( v[i] );
    }
    fout << st.size() << '\n';
    fout << fixed << setprecision( 12 );
    for ( auto x : st ) {
        fout << x.real() << ' ' << x.imag() << '\n';
    }
    return 0;
}