Cod sursa(job #2416521)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 27 aprilie 2019 17:42:07
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std ;
const int NR = 120005 ;
ifstream in ("infasuratoare.in") ;
ofstream out ("infasuratoare.out") ;

pair < double , double > v [ NR ] , st [ NR ] ;
int n ;

double det ( const pair < double , double > & i , const pair < double , double > & j , const pair < double , double > & k ) {
    return ( j.x - i.x )*( k.y - i.y ) - ( k.x - i.x )*( j.y - i.y ) ;
}
inline bool cmp ( const pair < double , double > & i , const pair < double , double > & j ) {
    return det( v [ 1 ] , i , j ) > 0 ;
}

int main() {
    int i , b , k ;
    in >> n ;
    for ( i = 1 ; i <= n ; ++ i )
        in >> v [ i ].x >> v [ i ].y ;
    b = 1 ;
    for ( i = 2 ; i <= n ; ++ i )
        if ( v [ i ] < v [ b ] )    b = i ;
    swap ( v [ b ] , v [ 1 ] ) ;
    sort ( v + 2 , v + n + 1 , cmp ) ;
    st [ 1 ] = v [ 1 ] ;
    st [ 2 ] = v [ 2 ] ;
    k = 2 ;

    for ( i = 3 ; i <= n ; ++ i )   {
        while ( k >= 2 && det( st [ k - 1 ] , st [ k ] , v [ i ] ) <= 0 )
            k -- ;
        st [ ++ k ] = v [ i ] ;
    }
    out << k << '\n' ;
    out << setprecision( 9 ) << fixed ;
    for ( i = 1 ; i <= k ; ++ i )
        out << st [ i ].x << ' ' << st [ i ].y << '\n' ;
}