Cod sursa(job #1922808)

Utilizator DysKodeTurturica Razvan DysKode Data 10 martie 2017 19:00:16
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

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

pair< double , double > v[120010];
int n,i,j,k,st[120010];

double sarrus( int a, int b, int c )
{
    double ans;
    ans = v[ a ].x * v[ b ].y + v[ b ].x * v[ c ].y + v[ c ].x * v[ a ].y - v[ b ].x * v[ a ].y - v[ c ].x * v[ b ].y - v[ a ].x * v[ c ].y;
    return ans;
}

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

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

    st[ 0 ] = 1;
    st[ 1 ] = 1;
    for( i = 3 ; i <= n ; i++ )
    {
        while( st[ 0 ] >= 2 && sarrus( st[ st[ 0 ] ] , st[ st[ 0 ] - 1 ] , i ) >= 0 ) st[ 0 ]--;
        st[ ++st[ 0 ] ] = i;
    }
    k = st[ 0 ];
    for( i = n - 1 ; i >= 1 ; i-- )
    {
        while( k - st[ 0 ] >= 1 && sarrus( st[ k ] , st[ k - 1 ] , i ) >= 0 ) k--;
        st[ ++k ] = i;
    }
    fout<<k-1<<'\n';
    for( i = 1 ; i < k ; i++ )
        fout<<fixed<<setprecision(12)<<v[ st[ i ] ].x<<' '<<v[ st[ i ] ].y<<'\n';

return 0;
}