Cod sursa(job #1257248)

Utilizator xtreme77Patrick Sava xtreme77 Data 7 noiembrie 2014 15:15:23
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
/*
 * Code by Spiromanul
 */

#include <fstream>
#include <bitset>
#include <algorithm>
#include <iomanip>

const double EPS = 1e-12 ;

const char IN [ ] = "infasuratoare.in" ;
const char OUT [ ] = "infasuratoare.out" ;
const int MAX = 120014 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

typedef pair < double , double > P ;

P puncte [ MAX ] ;
bitset < MAX > viz ;
int st [ MAX ] , varf ;

double determin ( const P &a , const P &b , const P &o )
{
    return ( 1LL * o.first * a.second + 1LL * a.first * b.second + 1LL * b.first * o.second - 1LL * a.second * b.first - 1LL * b.second * o.first - 1LL * a.first * o.second ) ;
}

int main(              )
{
    int n ;
    fin >> n ;
    for ( int i = 1 ; i <= n ; ++ i )
        fin >> puncte [ i ].first >> puncte [ i ].second ;

    sort ( puncte + 1 , puncte + n + 1 ) ;

    st [ 1 ] = 1 ;
    st [ 2 ] = 2 ;
    varf = 2 ;
    viz [ 2 ] = 1 ;
    int p = 1 ;

    for ( int i = 1 ; i > 0 ; i += ( p = ( i == n ) ? -p : p ) )
    {
        if ( viz [ i ] ) continue ;
        while ( varf >= 2 and determin ( puncte [ st [ varf - 1 ] ] , puncte [ st [ varf ] ] , puncte [ i ] ) < EPS )
            viz [ st [ varf -- ] ] = 0 ;
        st [ ++ varf ] = i ;
        viz [ i ] = 1 ;
    }
    fout << -- varf << '\n' ;
    for ( int i = 1 ; i <= varf ; ++ i )
        fout << fixed << setprecision ( 6 ) << puncte [ st [ i ] ].first << ' ' << puncte [ st [ i ] ].second << '\n' ;
    return 0;
}