Cod sursa(job #2724314)

Utilizator Tudor06MusatTudor Tudor06 Data 16 martie 2021 22:08:46
Problema Infasuratoare convexa Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 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;
}
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, 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 - 2 << '\n';
    for ( i = 0; i < d - 1; i ++ )
        fout << setprecision( 13 ) << down[i].x << ' ' << setprecision( 13 ) << down[i].y << '\n';
    for ( i = u - 1; i >= 1; i -- )
        fout << setprecision( 13 ) << up[i].x << ' ' << setprecision( 13 ) << up[i].y << '\n';
    return 0;
}