Cod sursa(job #2953602)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 11 decembrie 2022 19:20:52
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <algorithm>
#include <fstream>
#include <iomanip> 
#include <vector>
using namespace std;

ifstream cin( "infasuratoare.in" );
ofstream cout( "infasuratoare.out" );

struct points { 
    double x, y; 
};

vector<points> rez;
points v[ 120000 ];
int n, minn;

inline double isClockwise( const points& a, const points& b, const points& c ) {
    return ( b.y - a.y ) * ( c.x - b.x ) - ( b.x - a.x ) * ( c.y - b.y );
}

void infasurare() {
    rez.push_back( v[ 0 ] );
    rez.push_back( v[ 1 ] );
    for( int i = 2; i < n; ++i ) {
        while( isClockwise( rez[ rez.size() - 2 ], rez.back(), v[ i ] ) >= 0 )
            rez.pop_back();
        rez.push_back( v[ i ] );
    }
}

int main() 
{
    cin >> n;
    for( int i = 0; i < n; ++i ) {
        cin >> v[ i ].x >> v[ i ].y;
        if( v[ i ].y < v[ minn ].y )
            minn = i;
    }

    swap( v[ 0 ], v[ minn ] );
    sort( v + 1, v + n, []( const points& a, const points& b ) {
            return isClockwise( v[ 0 ], a, b ) < 0;
        } );

    infasurare();
    cout << rez.size() << '\n';
    cout << fixed << std::setprecision(9); 
    for( const points& p : rez )
        cout << p.x << ' ' << p.y << '\n';
    return 0;
}