Pagini recente » Cod sursa (job #1806193) | Cod sursa (job #1885267) | Cod sursa (job #208480) | Rating Florin Marian (florinmarianb) | Cod sursa (job #362999)
Cod sursa(job #362999)
#include <algorithm>
using namespace std;
#define DIM 120001
#define INF ( 1<<30 )
struct pct {
double x, y;
};
int O;
int n, ind[ DIM ], stv[ DIM ];
pct a[ DIM ];
inline double panta( int A, int B ) {
if( a[ A ].x == a[ B ].x )
return INF;
return ( ( double )a[ A ].y - a[ B ].y )/( a[ A ].x - a[ B ].x );
}
inline double semn( int A, int B, int C ) {
return ( double )a[ A ].x*a[ B ].y + a[ B ].x*a[ C ].y + a[ C ].x*a[ A ].y - a[ A ].y*a[ B ].x - a[ B ].y*a[ C ].x - a[ C ].y*a[ A ].x;
}
int cmp( int A, int B ) {
return panta( O, A ) > panta( O, B );
}
int main() {
freopen( "infasuratoare.in", "r", stdin );
freopen( "infasuratoare.out", "w", stdout );
int i, vf;
scanf( "%d", &n );
for( i = 1; i <= n; ++i )
scanf( "%lf %lf", &a[ i ].x, &a[ i ].y );
O = 1;
for( i = 2; i <= n; ++i ) {
if( a[ i ].x < a[ O ].x )
O = i;
else if( a[ i ].x == a[ O ].x && a[ i ].y < a[ O ].y )
O = i;
}
for( i = 1; i <= n; ++i )
ind[ i ] = i;
sort( ind+1, ind+n+1, cmp );
vf = 0;
stv[ vf ] = O;
for( i = 1; i <= n; ++i )
if( ind[ i ] != O ) {
for( ; vf >= 1 && semn( stv[ vf-1 ], stv[ vf ], ind[ i ] ) > 0; --vf );
stv[ ++vf ] = ind[ i ];
}
printf( "%d\n", vf+1 );
for( i = vf; i >= 0; --i )
printf( "%lf %lf\n", a[ stv[ i ] ].x, a[ stv[ i ] ].y );
return 0;
}