Pagini recente » Cod sursa (job #2729955) | Cod sursa (job #1197804) | Cod sursa (job #3173342) | Cod sursa (job #2985880) | Cod sursa (job #1438374)
#include <fstream>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define Nmax 120002
#define eps ( 1 / ( 1e12 ) )
FILE *f = fopen ( "infasuratoare.in", "r" );
FILE *g = fopen ( "infasuratoare.out", "w" );
struct point{
double x, y;
} v[Nmax];
int N, L, Hull[Nmax];
bool cmp ( point A, point B ){
if ( abs ( A.x - B.x ) < eps )
return A.y < B.y;
return A.x < B.x;
}
double crossp ( point A, point B, point C ){
return A.x * ( B.y - C.y ) + B.x * ( C.y - A.y ) + C.x * ( A.y - B.y );
}
void ConvexHull(){
for ( int i = 1; i <= N; ++i ){
while ( L > 1 && crossp ( v[Hull[L-1]], v[Hull[L]], v[i] ) <= 0 )
L--;
Hull[++L] = i;
}
int l = L;
for ( int i = N; i >= 1; --i ){
while ( L > l && crossp ( v[Hull[L-1]], v[Hull[L]], v[i] ) <= 0 )
L--;
Hull[++L] = i;
}
L--;
}
int main(){
fscanf ( f, "%d", &N );
for ( int i = 1; i <= N; ++i )
fscanf ( f, "%lf%lf", &v[i].x, &v[i].y );
sort ( v + 1, v + N + 1, cmp );
ConvexHull();
fprintf ( g, "%d\n", L );
for ( int i = 1; i <= L; ++i )
fprintf ( g, "%.6lf %.6lf\n", v[Hull[i]].x, v[Hull[i]].y );
return 0;
}