Cod sursa(job #2744965)

Utilizator Tudor06MusatTudor Tudor06 Data 25 aprilie 2021 16:47:03
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <cstdio>
#include <fstream>
#include <deque>
#include <algorithm>
#include <iomanip>

using namespace std;


#define ld long double
#define x first
#define y second

const int NMAX = 12e4;


pair<ld, ld> v[NMAX];

deque <int> dq;

bool cmp( pair<ld,ld> a, pair<ld, ld> b ) {
    return   ( a.y - v[dq.front()].y ) * ( b.x - v[dq.front()].x ) >
             ( b.y - v[dq.front()].y ) * ( a.x - v[dq.front()].x );
}

bool cmp2( int i, int j ) {
    return  ( v[dq[i]].x - v[dq[i - 1]].x ) * ( v[j].y - v[dq[i - 1]].y ) >
            ( v[j].x - v[dq[i - 1]].x ) * ( v[dq[i]].y - v[dq[i - 1]].y );
}
int main() {
    ifstream fin( "infasuratoare.in" );
    ofstream fout( "infasuratoare.out" );

    int n, i, minim = 0;
    fin >> n;
    for ( i = 0; i < n; i ++ ) {
        fin >> v[i].x >> v[i].y;
        if ( v[i].x <= v[minim].x ) {
            minim = i;
        }
    }
    swap( v[0], v[minim] );
    dq.push_back( 0 );
    sort( v + 1, v + n, cmp );
    for ( i = 1; i < n; i ++ ) {
        while ( dq.size() > 1 && cmp2( dq.size() - 1, i ) )
            dq.pop_back();
        dq.push_back( i );
    }
    fout << dq.size() << '\n';
    for ( i = dq.size() - 1; i >= 0; i -- ) {
        fout << fixed << setprecision( 12 ) << v[dq[i]].x << ' ' << v[dq[i]].y << '\n';
    }
    return 0;
}