Cod sursa(job #362999)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 11 noiembrie 2009 15:08:18
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <algorithm>
using namespace std;

#define DIM 120001
#define INF ( 1<<30 )

struct pct {

    double x, y;
};

int O;
int n, ind[ DIM ], stv[ DIM ];
pct a[ DIM ];

inline double panta( int A, int B ) {

    if( a[ A ].x == a[ B ].x )
        return INF;

    return ( ( double )a[ A ].y - a[ B ].y )/( a[ A ].x - a[ B ].x );
}

inline double semn( int A, int B, int C ) {

    return ( double )a[ A ].x*a[ B ].y + a[ B ].x*a[ C ].y + a[ C ].x*a[ A ].y - a[ A ].y*a[ B ].x - a[ B ].y*a[ C ].x - a[ C ].y*a[ A ].x;
}

int cmp( int A, int B ) {

    return panta( O, A ) > panta( O, B );
}

int main() {

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

    int i, vf;

    scanf( "%d", &n );
    for( i = 1; i <= n; ++i )
        scanf( "%lf %lf", &a[ i ].x, &a[ i ].y );

    O = 1;
    for( i = 2; i <= n; ++i ) {

        if( a[ i ].x < a[ O ].x )
            O = i;
        else if( a[ i ].x == a[ O ].x && a[ i ].y < a[ O ].y )
            O = i;
    }
    for( i = 1; i <= n; ++i )
        ind[ i ] = i;
    sort( ind+1, ind+n+1, cmp );
    vf = 0;
    stv[ vf ] = O;
    for( i = 1; i <= n; ++i )
        if( ind[ i ] != O ) {

            for( ; vf >= 1 && semn( stv[ vf-1 ], stv[ vf ], ind[ i ] ) > 0; --vf );
            stv[ ++vf ] = ind[ i ];
        }

    printf( "%d\n", vf+1 );
    for( i = vf; i >= 0; --i )
        printf( "%lf %lf\n", a[ stv[ i ] ].x, a[ stv[ i ] ].y );

    return 0;
}