Cod sursa(job #1118218)

Utilizator drobertDumitru Robert drobert Data 24 februarie 2014 09:00:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream cin( "infasuratoare.in" );
ofstream cout( "infasuratoare.out" );

#define pb push_back
#define mp make_pair
#define st first
#define nd second

int n, poz = 1, lev;
pair< double,double > p[ 120010 ], stack[ 120010 ];

double lor( pair< double,double > a,pair< double,double > b,pair< double,double > c )
{
	return ( b.st - a.st ) * ( c.nd - a.nd ) - (b.nd - a.nd) * (c.st - a.st);
}

bool cmp( pair< double,double > a,pair< double,double > b)
{
    return lor( p[ 1 ],a,b ) < 0;
}

int main()
{
	cin >> n;
	for ( int i = 1; i <= n; i++ )
	{
		cin >> p[ i ].st >> p[ i ].nd;
		if ( p[ i ] < p[ poz ] )
			poz = i;
	}
	swap( p[ poz ],p[ 1 ] );
	sort( p + 2,p + n + 1,cmp );
	stack[ ++lev ] = p[ 1 ];
	stack[ ++lev ] = p[ 2 ];
	for ( int i = 3; i <= n; i++ )
	{
		while ( lev > 1 && lor( stack[ lev - 1 ],stack[ lev ],p[ i ] ) > 0 )
			lev--;
		stack[ ++lev ] = p[ i ];
	}
	cout << lev << '\n';
	for ( int i = lev; i >= 1; i-- )
		cout << fixed << setprecision( 9 ) << stack[ i ].st << " " << stack[ i ].nd << '\n';
}