Cod sursa(job #1257258)

Utilizator xtreme77Patrick Sava xtreme77 Data 7 noiembrie 2014 15:25:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 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 ( P O , P A , P B )
{
    return (A.first - O.first) * (B.second - O.second) - (B.first - O.first) * (A.second - 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;
}