Cod sursa(job #412314)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 5 martie 2010 14:47:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <algorithm>
#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

int N;
vector <int> s;
vector < pair <double, double> > p;

inline double pnt( const pair <double, double> p_1, const pair <double, double> p_2 ) {

    if( p_1.first == p_2.first )
        return INF;

    return ( p_1.second - p_2.second ) / ( p_1.first - p_2.first );
}

inline double sgn( const pair <double, double> p_1, const pair <double, double> p_2, const pair <double, double> p_3 ) {

    return ( p_3.second - p_1.second ) * ( p_2.first - p_1.first ) - ( p_3.first - p_1.first ) * ( p_2.second - p_1.second );
}

struct cmp {

    bool operator()( const pair <double, double> &p_1, const pair <double, double> &p_2 ) {

        return pnt( p[ 0 ], p_1 ) < pnt( p[ 0 ], p_2 );
    }
};

int main() {

    freopen( "infasuratoare.in", "r", stdin );
    freopen( "infasuratoare.out", "w", stdout );

    int i;
    vector <int> :: iterator it;

    scanf( "%d", &N );

    p.resize( N );
    for( i = 0; i < N; ++i ) {

        scanf( "%lf %lf", &p[ i ].first, &p[ i ].second );

        if( p[ i ].first < p[ 0 ].first )
            swap( p[ i ], p[ 0 ] );
        else if( p[ i ].first == p[ 0 ].first && p[ 0 ].second < p[ 0 ].second )
            swap( p[ i ], p[ 0 ] );
    }

    sort( p.begin() + 1, p.end(), cmp() );

    s.push_back( 0 );
    for( i = 1; i < N; ++i ) {

        while( s.size() > 2 && sgn( p[ s[ s.size() - 2 ] ], p[ s[ s.size() - 1 ] ], p[ i ] ) < 0 )
            s.pop_back();
        s.push_back( i );
    }

    printf( "%d\n", s.size() );
    for( it = s.begin(); it != s.end(); ++it )
        printf( "%lf %lf\n", p[ *it ].first,p[ *it ].second );

    return 0;
}