Pagini recente » Cod sursa (job #1827825) | Cod sursa (job #1178982) | Cod sursa (job #2322031) | Cod sursa (job #2345599) | Cod sursa (job #1922857)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
pair< long double , long double > v[120010];
int n,i,j,k,st[120010];
long double sarrus( int a, int b, int c )
{
long 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 = 2 ; i <= n ; i++ )
{
while( st[ 0 ] >= 2 && sarrus( st[ st[ 0 ] - 1 ] , st[ st[ 0 ] ] , 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 - 1 ] , st[ k ] , i ) < 0 ) k--;
st[ ++k ] = i;
}
fout<<k-1<<'\n';
for( i = 1 ; i < k ; i++ )
fout<<fixed<<setprecision(6)<<v[ st[ i ] ].x<<' '<<v[ st[ i ] ].y<<'\n';
return 0;
}