Cod sursa(job #2724851)

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

using namespace std;

const int NMAX = 12e4;


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

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

long 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 );
}

long double read_double(FILE *fin) {
    char ch = fgetc(fin);

    while (ch != '-' && ch != '.' && (ch < '0' || ch > '9'))
        ch = fgetc(fin);

    long double sgn = 1;
    if (ch == '-') {
        sgn = -1;
        ch = fgetc(fin);
    }

    long double ans = 0;
    while (ch >= '0' && ch <= '9') {
        ans = ans * 10 + (ch - '0');
        ch = fgetc(fin);
    }

    if (ch == '.') {
        long double p10 = 0.1;
        ch = fgetc(fin);
        while (ch >= '0' && ch <= '9') {
            ans += p10 * ( ch - '0' );
            p10 *= 0.1;
            ch = fgetc(fin);
        }
    }

    return ans * sgn;
}

int main() {
    FILE *fin = fopen( "infasuratoare.in", "r" ), *fout = fopen( "infasuratoare.out", "w" );
    int n, i, u, d;
    fscanf(fin, "%d", &n);
//    printf("%d\n", n); return 0;
    for ( i = 0; i < n; i ++ ) {
        v[i].x = read_double(fin);
        v[i].y = read_double(fin);
//        printf("%f %f\n", 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 ++;
        }
    }
    fprintf( fout, "%d\n", d + u - egal( down[0], up[0] ) - egal( down[d - 1], up[u - 1] ) );

    for ( i = 0; i < d - egal( down[d - 1], up[d - 1] ); i ++ )
        fprintf( fout, "%.13Lf %.13Lf\n", down[i].x, down[i].y );
    for ( i = u - 1; i >= 0 + egal( down[0], up[0] ); i -- )
        fprintf( fout, "%.13Lf %.13Lf\n", up[i].x, up[i].y );

    fclose( fin );
    fclose( fout );
    return 0;
}