Pagini recente » Monitorul de evaluare | Cod sursa (job #2273269) | Cod sursa (job #3241034) | Cod sursa (job #1535306) | Cod sursa (job #1703624)
#include <bits/stdc++.h>
const int DIM = 1 << 17;
const double EPS = 0.000000000001;
using namespace std;
int N, K, S[DIM];
struct point{ double x, y; } P[DIM];
inline double cross_product( point A, point B, point C ) {
return (C.x - A.x) * (B.y - A.y) - (B.x - A.x) * (C.y - A.y);
}
inline bool cmp( point A, point B ) {
return cross_product( P[1], A, B ) < 0;
}
int main() {
FILE *input_file = fopen( "infasuratoare.in" , "r" );
FILE *output_file = fopen( "infasuratoare.out", "w" );
fscanf( input_file, "%d", &N );
for( int i = 1; i <= N; i ++ ) {
fscanf( input_file, "%lf %lf", &P[i].x, &P[i].y );
if( P[i].x < P[1].x )
swap( P[1], P[i] );
else
if( fabs( P[i].x - P[1].x ) < EPS ) {
if( P[i].y < P[1].y )
swap( P[1], P[i] );
}
}
sort( P + 2, P + N + 1, cmp );
S[++K] = 1; S[++K] = 2;
for( int i = 3; i <= N; i ++ ) {
while( K >= 2 && cross_product( P[ S[K - 1] ], P[ S[K] ], P[i] ) > 0 )
K --;
S[++K] = i;
}
fprintf( output_file, "%d\n", K );
for( int i = 1; i <= K; i ++ )
fprintf( output_file, "%.12lf %.12lf\n", P[ S[i] ].x, P[ S[i] ].y );
return 0;
}