Pagini recente » Cod sursa (job #843801) | Cod sursa (job #768927) | Cod sursa (job #2078988) | tema | Cod sursa (job #840471)
Cod sursa(job #840471)
#include <fstream>
using namespace std;
ifstream f ( "infasuratoare.in" );
ofstream g ( "infasuratoare.out" );
#include <algorithm>
#define LE 166600
#include <iomanip>
#include <vector>
pair<double, double> A[LE];
int ST[LE];
#define inf 1<<30
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;
A[0] = make_pair ( inf, inf );
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 ) if ( i != minim )
{
A[i].first -= A[minim].first;
A[i].second -= A[minim].second;
}
swap ( A[minim], A[n--] );
head = n + 1;
sort ( A + 1, A + n + 1, comp );
ST[1] = head;
ST[2] = 1;
l = 2;
for ( i = 2; i <= n; ++i )
{
while ( cross_product ( A[ST[l-1]], A[ST[l]], A[i] ) > 0 && l >= 2 )
--l;
ST[++l] = i;
}
while ( l >= 2 && cross_product ( A[ST[l-1]], A[ST[l]], A[1] ) > 0 )
--l;
g << fixed;
g << setprecision ( 13 );
g << l << '\n';
for ( i = 1; i <= l; ++i )
g << A[ST[i]].first + needAdd.first << " " << A[ST[i]].second + needAdd.second << '\n';
f.close();
g.close();
return 0;
}