Cod sursa(job #1596376)

Utilizator DysKodeTurturica Razvan DysKode Data 10 februarie 2016 22:40:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

typedef pair<double,double> pii;
#define x first
#define y second

pii v[120010],CH[120010];
int n,i,k,f;

inline double sarrus( pii A, pii B, pii C )
{
    return ( ( A.x * B.y + B.x * C.y + C.x * A.y ) - ( C.x * B.y + A.x * C.y + B.x * A.y ) );
}

int main()
{
    fin>>n;
    for( i = 1 ; i <= n ; i++ )
        fin>>v[ i ].x>>v[ i ].y;

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

    for( i = 1 ; i <= n ; i++ )
    {
        while( k >= 2 && sarrus( CH[ k - 1 ] , CH[ k ] , v[ i ] ) <= 0 )
            k--;
        CH[ ++k ] = v[ i ];
    }

    f = k;
    for( i = n - 1 ; i >= 1 ; i-- )
    {
        while( k >= f + 1 && sarrus( CH[ k - 1 ] , CH[ k ] , v[ i ] ) <= 0 )
            k--;
        CH[ ++k ] = v[ i ];
    }

    fout<<k-1<<'\n';
    fout<<setprecision(6)<<fixed;
    for( i = 1 ; i < k ; i++ )
    {
        fout<<CH[ i ].x<<' '<<CH[ i ].y<<'\n';
    }

    return 0;
}