Pagini recente » Cod sursa (job #515797) | Cod sursa (job #1725796) | Cod sursa (job #922516) | Cod sursa (job #559180) | Cod sursa (job #840494)
Cod sursa(job #840494)
#include <fstream>
using namespace std;
ifstream f ( "infasuratoare.in" );
ofstream g ( "infasuratoare.out" );
#include <algorithm>
#define LE 166600
#include <iomanip>
#include <vector>
#define double long double
pair<double, double> A[LE];
int ST[LE];
int i, n, head, minim, l;
inline double cross_product ( pair<double, double> IN, pair<double, double> P1, pair<double, double> P2 )
{
return ( P1.first - IN.first ) * ( P2.second - IN.second ) - ( P1.second - IN.second ) * ( P2.first - IN.first );
}
bool comp ( pair<double, double> P1, pair<double, double> P2 )
{
return P1.first * P2.second < P2.first * P1.second;
}
int main()
{
f >> n;
minim=1;
for ( i = 1; i <= n; ++i )
{
f >> A[i].first >> A[i].second;
if ( A[i].second < A[minim].second || ( A[i].second == A[minim].second && A[i].first < A[minim].first ) )
minim = i;
}
pair<double, double>needAdd = A[minim];
for ( i = 1; i <= n; ++i )
{
A[i].first -= needAdd.first;
A[i].second -= needAdd.second;
}
swap ( A[minim], A[1] );
sort ( A + 2, A + n + 1, comp );
ST[1] = 1;
ST[2] = 2;
l = 2;
for ( i = 3; i <= n; ++i )
{
while ( cross_product ( A[ST[l-1]], A[ST[l]], A[i] ) >= 0 && l >= 2 )
--l;
ST[++l] = i;
}
int okz = 0;
while ( l >= 2 && cross_product ( A[ST[l-1]], A[ST[l]], A[1] ) >= 0 )
{
--l;
okz = 1;
}
if ( okz == 1 ) ++l;
g << fixed;
g << setprecision ( 15 );
g << l << '\n';
for ( i = l; i >=1; --i )
g << A[ST[i]].first + needAdd.first << " " << A[ST[i]].second + needAdd.second << '\n';
f.close();
g.close();
return 0;
}