Pagini recente » Cod sursa (job #2471446) | Cod sursa (job #2265556) | Cod sursa (job #102746) | Cod sursa (job #1554428) | Cod sursa (job #1650014)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define x first
#define y second
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double,double> v[120010],CH[120010];
int n,a,b,c,i,j,k,f;
int sarrus( pair<double,double> a, pair<double,double> b, pair<double,double> c )
{
return ( ( a.x * b.y + b.x * c.y + c.x * a.y ) -
( a.y * b.x + b.y * c.x + c.y * a.x ) );
}
int main()
{
fin>>n;
for( i = 1 ; i <= n ; i++ )
fin>>v[ i ].x>>v[ i ].y;
for( i = 1 ; i <= n ; i++ )
{
while( k >= 2 && sarrus( CH[ k - 1 ] , CH[ k ] , v[ i ] ) < 0 )
k--;
CH[ ++k ] = v[ i ];
}
f = k;
for( i = n - 1 ; i >= 1 ; i-- )
{
while( f - k >= 1 && sarrus( CH[ f - 1 ] , CH[ f ] , v[ i ] ) < 0 )
f--;
CH[ ++f ] = v[ i ];
}
fout<<f-1<<'\n';
for( i = 1 ; i < f ; i++ )
fout<<fixed<<setprecision(12)<<CH[ i ].x<<' '<<CH[ i ].y<<'\n';
return 0;
}