Pagini recente » Cod sursa (job #1006842) | Cod sursa (job #2047837) | Cod sursa (job #2890633) | Cod sursa (job #3224279) | Cod sursa (job #1112021)
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct valiPair {
double x, y, sinus;
} maxK, k;
long n;
double x, y;
bool pb;
vector<valiPair> q, v;
inline double myDistance ( valiPair p1, valiPair p2 ) {
return sqrt ( ( p2.x - p1.x ) * ( p2.x - p1.x ) + ( p2.y - p1.y ) * ( p2.y - p1.y ) );
}
inline double sinus ( valiPair p1, valiPair p2 ) {
if ( p1.x == p2.x && p1.y == p2.y ) return 2;
else return ( p2.y - p1.y ) / myDistance ( p1, p2 );
}
bool cmp ( valiPair p1, valiPair p2 ) {
return p1.sinus > p2.sinus;
}
inline bool leftTurn ( valiPair p1, valiPair p2, valiPair p3 ) {
if ( p1.x == p2.x )
return ( p2.y - p1.y ) * ( p2.x - p3.x ) > 0;
else {
double m = ( p2.y - p1.y ) / ( p2.x - p1.x ),
n = p1.y - m * p1.x;
return ( p2.x - p1.x ) * ( p3.y - ( m * p3.x + n ) ) > 0;
}
}
int main()
{
freopen ( "infasuratoare.in", "r", stdin );
freopen ( "infasuratoare.out", "w", stdout );
scanf ( "%ld", &n );
maxK.x = maxK.y = 999999;
for ( long i = 1; i <= n; i++ ) {
scanf ("%lf %lf", &x, &y);
k.x = x; k.y = y;
v.push_back ( k );
if ( k.x < maxK.x || ( k.x == maxK.x && k.y < maxK.y ) )
maxK = k;
}
for ( long i = 0; i < v.size ( ); i++ )
v[i].sinus = sinus ( maxK, v[i] );
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].x, q[i].y );
return 0;
}