Cod sursa(job #2724253)

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

using namespace std;

const int NMAX = 1e5;


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

deque <coord> ans[2];

bool rel_pos( coord a, coord b, coord c, int dir ) {
    double cy = a.y + (c.x - a.x) * ( b.y - a.y ) / ( b.x - a.x );
    if ( dir == 1 ) {
        return c.y >= cy;
    }
    return c.y <= cy;
}

void add( coord a, int dir ) { /// 1 - up
    while ( ans[dir].size() > 1 && !rel_pos( ans[dir][ans[dir].size() - 2], a, ans[dir].back(), dir ) ) {
        ans[dir].pop_back();
    }
    ans[dir].push_back( a );
}

bool cmp( coord a, coord b ) {
    return a.x < b.x;
}
int main() {
    ifstream fin( "infasuratoare.in" );
    ofstream fout( "infasuratoare.out" );
    int n, i;
    fin >> n;
    for ( i = 0; i < n; i ++ ) {
        fin >> v[i].x >> v[i].y;
    }
    sort( v, v + n, cmp );
    ans[0].push_back( v[n - 1] );
    ans[1].push_back( v[0] );
    ///cout << v[0].x << ' ' << v[0].y << endl << v[n-1].x << ' ' << v[n-1].y;
    for ( i = 1; i < n - 1; i ++ ) {
        if ( rel_pos( v[0], v[n - 1], v[i], 1 ) == 1 )
            add( v[i], 1 );
    }
    for ( i = n - 1; i >= 1; i -- ) {
        if ( rel_pos( v[0], v[n - 1], v[i], 1 ) == 0 )
            add( v[i], 0 );
    }
    fout << ans[1].size() + ans[0].size() << '\n';
    for ( int j = 1; j >= 0; j -- ) {
        for ( i = 0; i < ans[j].size(); i ++ )
            fout << ans[j][i].x << ' ' << ans[j][i].y << '\n';

    }
    return 0;
}