Cod sursa(job #2416520)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 27 aprilie 2019 17:39:39
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 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 i.x*j.y + j.x*k.y + k.x*i.y - i.y*j.x - j.y*k.x - k.y*i.x ;  // e recomandata forma initiala pt ca sunt mai putine operatii si scade prababilitatea unei erori
}
inline bool cmp ( const pair < double , double > & i , const pair < double , double > & j ) {
    return det( v [ 1 ] , i , j ) > 0 ;
}
/*
    det > 0 - triunghiul are varful in jos
    det > 0 - este convex
    sortarea de face astfel descrescator in functie de cate alte puncte sunt " deasupra" dreptei care uneste 1 cu x ;
*/
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 = 1 ; i <= n ; ++ i ) cout << v [ i ].x << ' ' << v [ i ].y << '\n' ;

    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' ;
}