Cod sursa(job #1650014)

Utilizator DysKodeTurturica Razvan DysKode Data 11 martie 2016 16:10:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

#define x first
#define y second

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

pair<double,double> v[120010],CH[120010];
int n,a,b,c,i,j,k,f;

int sarrus( pair<double,double> a, pair<double,double> b, pair<double,double> c )
{
    return ( ( a.x * b.y + b.x * c.y + c.x * a.y ) -
             ( a.y * b.x + b.y * c.x + c.y * a.x ) );
}

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

    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( f - k >= 1 && sarrus( CH[ f - 1 ] , CH[ f ] , v[ i ] ) < 0 )
            f--;
        CH[ ++f ] = v[ i ];
    }
    fout<<f-1<<'\n';
    for( i = 1 ; i < f ; i++ )
        fout<<fixed<<setprecision(12)<<CH[ i ].x<<' '<<CH[ i ].y<<'\n';

return 0;
}