Pagini recente » Cod sursa (job #2133153) | Cod sursa (job #1645536) | Cod sursa (job #1113037) | Cod sursa (job #75736) | Cod sursa (job #1112005)
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
long n;
double x, y;
bool pb;
vector<pair<double, double> > q, v;
pair<double, double> maxP ( 99999, 99999 );
inline double myDistance ( pair<double, double> p1, pair<double, double> p2 ) {
return sqrt ( pow ( p2.first - p1.first, 2 ) + pow ( p2.second - p1.second, 2 ) );
}
inline double sinus ( pair<double, double> p1, pair<double, double> p2 ) {
if ( p1 == p2 ) return 2;
else
return ( p2.second - p1.second ) / myDistance ( p1, p2 );
}
bool cmp ( pair<double, double> p1, pair<double, double> p2 ) {
return sinus ( maxP, p1 ) > sinus ( maxP, p2 );
}
inline bool leftTurn ( pair<double, double> p1, pair<double, double> p2, pair<double, double> p3 ) {
if ( p1.first == p2.first )
return ( p2.second - p1.second ) * ( p2.first - p3.first ) > 0;
else {
double m = ( p2.second - p1.second ) / ( p2.first - p1.first ),
n = p1.second - m * p1.first;
return ( p2.first - p1.first ) * ( p3.second - ( m * p3.first + n ) ) > 0;
}
}
int main()
{
freopen ( "infasuratoare.in", "r", stdin );
freopen ( "infasuratoare.out", "w", stdout );
scanf ( "%ld", &n );
for ( long i = 1; i <= n; i++ ) {
scanf ("%lf %lf", &x, &y),
v.push_back ( make_pair ( x, y ) );
if ( v.back ( ) < maxP )
maxP = v.back ( );
}
sort ( v.begin ( ), v.end ( ), cmp );
for ( long i = 0; i < v.size ( ); i++ ) {
while ( q.size ( ) > 1 && leftTurn ( q[q.size ( ) - 2], q[q.size ( ) - 1], v[i] ) )
q.pop_back ( );
q.push_back ( v[i] );
}
printf ( "%ld\n", q.size ( ) );
for ( long i = q.size ( ) - 1; i >= 0; i-- )
printf ( "%lf %lf\n", q[i].first, q[i].second);
return 0;
}