Cod sursa(job #2288758)

Utilizator Turturica_DorinTurturica Dorin Turturica_Dorin Data 23 noiembrie 2018 20:33:15
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

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

#define pp pair< double, double >
#define x first
#define y second
pp p[ 120005 ];

int st[ 120005 ], n, i, val;

double determinant( pp a, pp b, pp c )
{
    double ans = a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
    return ans;
}

int main()
{
    fin >> n;
    for ( i = 1; i <= n; i++ )
    {
        fin>> p[ i ].x >> p[ i ].y;
    }
    sort( p + 1, p + n + 1 );
    st[ ++st[ 0 ] ] = 1;
    st[ ++st[ 0 ] ] = 2;
    for ( i = 3; i <= n; i++ )
    {
        while ( st[ 0 ] >= 2 && determinant( p[ st[ st[ 0 ] - 1 ] ], p[ st[ st[ 0 ] ] ], p[ i ] ) > 0 )
        {
            st[ 0 ]--;
        }
        st[ ++st[ 0 ] ] = i;
    }
    for ( i = n - 1; i >= 1; i-- )
    {
        while ( determinant( p[ st[ st[ 0 ] - 1 ] ], p[ st[ st[ 0 ] ] ], p[ i ] ) > 0 )
        {
            st[ 0 ]--;
        }
        st[ ++st[ 0 ] ] = i;
    }
    st[ 0 ]--;
    fout<< st[ 0 ] << '\n';
    for ( i = st[ 0 ]; i >= 1; i-- )
    {
        fout<< fixed << setprecision ( 12 ) << p[ st[ i ] ].x << ' ' << p[ st[ i ] ].y << '\n';
    }
    return 0;
}