Cod sursa(job #3288851)

Utilizator David_Popa123Popa David Matei David_Popa123 Data 24 martie 2025 16:00:53
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );

#define MAXN 120000
struct ura {
    double x, y;
    int plan;
} v[MAXN + 1], a, b;

ura st[MAXN + 1];

bool cmp( ura a, ura b ) {
    return ( a.x < b.x || ( a.x == b.x && a.y < b.y ) );
}

int arie( ura a, ura b, ura c ) {
    return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}

int main() {
    int n, i, niv, niv2;

    fin >> n;
    for( i = 1; i <= n; i++ )
        fin >> v[i].x >> v[i].y;

    sort( v + 1, v + n + 1, cmp );

    a = v[1];
    b = v[n];
    for( i = 2; i <= n - 1; i++ )
        if( arie( a, b, v[i] ) > 0 )
            v[i].plan = 1;
        else if( arie( a, b, v[i] ) < 0 )
            v[i].plan = 2;

    niv = 0;
    st[++niv] = v[1];
    for( i = 2; i <= n; i++ ) {
        if( v[i].plan < 2 ) { //0 sau 1
            while( niv > 1 && arie( st[niv - 1], st[niv], v[i] ) > 0 )
                niv--;
            st[++niv] = v[i];
        }
    }

    niv2 = niv;
    st[niv] = v[n];
    for( i = n - 1; i > 0; i-- ) {
        if( ( v[i].plan & 1 ) == 0 ) { //0 sau 2
            while( niv > niv2 && arie( st[niv - 1], st[niv], v[i] ) > 0 )
                niv--;
            st[++niv] = v[i];
        }
    }

    niv--;
    fout << niv << '\n';
    for( i = niv; i > 0; i-- )
        fout << fixed << setprecision( 6 ) << st[i].x << ' ' << st[i].y << '\n';
    return 0;
}