Cod sursa(job #2724870)

Utilizator Tudor06MusatTudor Tudor06 Data 18 martie 2021 00:16:35
Problema Infasuratoare convexa Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <iomanip>

using namespace std;

const int NMAX = 12e4;


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.x - a.x ) * ( b.y - a.y );
}


bool cmp1( coord a, coord b ) {
    if ( a.x < b.x )
        return 1;
    if ( a.x == b.x )
        return a.y < b.y;
    return 0;
}
bool cmp2( coord a, coord b ) {
    if ( a.x < b.x )
        return 1;
    if ( a.x == b.x )
        return a.y > b.y;
    return 0;
}

bool egal( coord a, coord b ) {
    return ( a.x == b.x && a.y == b.y );
}
int main() {
    ifstream fin( "infasuratoare.in" );
    ofstream fout( "infasuratoare.out" );
    ios_base::sync_with_stdio(false);
    fin.tie(0);fout.tie(0);
    int n, i, u, d;
    fin >> n;
    for ( i = 0; i < n; i ++ ) {
        fin >> v[i].x >> v[i].y;
    }
    sort( v, v + n, cmp1 );
    u = d = 0;
    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 ++;
        }
    }
    sort( v, v + n, cmp2 );
    for ( i = 0; i < n; i ++ ) {
        if ( rel_pos( v[0], v[n - 1], v[i] ) >= v[i].y ) {
            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 - egal( down[0], up[0] ) - egal( down[d - 1], up[u - 1] ) << '\n';

    for ( i = 0; i < d - egal( down[d - 1], up[d - 1] ); i ++ )
        fout << fixed << setprecision( 13 ) << down[i].x << ' ' << setprecision( 13 ) << down[i].y << '\n';
    for ( i = u - 1; i >= 0 + egal( down[0], up[0] ); i -- )
        fout << setprecision( 13 ) << up[i].x << ' ' << setprecision( 13 ) << up[i].y << '\n';
    return 0;
}