Pagini recente » Cod sursa (job #737751) | Cod sursa (job #325059) | Cod sursa (job #2223703) | Cod sursa (job #2610766) | Cod sursa (job #1118218)
#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';
}