Cod sursa(job #2724274)

Utilizator Tudor06MusatTudor Tudor06 Data 16 martie 2021 20:50:59
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <iomanip>

using namespace std;

const int NMAX = 1e5;


struct coord {
    double x;
    double y;
} v[NMAX];

deque <coord> up;
deque <coord> down;

double rel_pos( coord a, coord b, coord c ) {
    return a.y + (c.x - a.x) * ( b.y - a.y ) / ( b.x - a.x );
}


bool cmp( coord a, coord b ) {
    return a.x < b.x;
}
int main() {
    ifstream fin( "infasuratoare.in" );
    ofstream fout( "infasuratoare.out" );
    int n, i, u, d;
    fin >> n;
    for ( i = 0; i < n; i ++ ) {
        fin >> v[i].x >> v[i].y;
    }
    sort( v, v + n, cmp );
    u = d = 0;
    ///cout << v[0].x << ' ' << v[0].y << endl << v[n-1].x << ' ' << v[n-1].y;
    for ( i = 0; i < n; i ++ ) {
        if ( rel_pos( v[0], v[n - 1], v[i] ) <= v[i].y ) {
            while ( u > 1 && rel_pos( up[u - 2], v[i], up[u - 1] ) >= up[u - 1].y ) {
                up.pop_back();
                u --;
            }
            up.push_back( v[i] );
            u ++;
        } else {
            while ( d > 1 && rel_pos( down[d - 2], v[i], down[d - 1] ) <= down[d - 1].y ) {
                down.pop_back();
                d --;
            }
            down.push_back( v[i] );
            d ++;
        }
    }
    fout << d + u << '\n';
    for ( i = 0; i < u; i ++ )
        fout << setprecision( 13 ) << up[i].x << ' ' << setprecision( 13 ) << up[i].y << '\n';
    for ( i = d - 1; i >= 0; i -- )
        fout << setprecision( 13 ) << down[i].x << ' ' << setprecision( 13 ) << down[i].y << '\n';
    return 0;
}