Pagini recente » Cod sursa (job #547977) | Cod sursa (job #2128109) | Cod sursa (job #2888995) | Cod sursa (job #1467926) | Cod sursa (job #1365923)
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 120002
FILE *f = fopen ( "infasuratoare.in", "r" );
FILE *g = fopen ( "infasuratoare.out", "w" );
struct point{
double x, y;
}v[Nmax], Q[Nmax];
int N, L;
bool cmp ( point A, point B ){
if ( A.x == B.x )
return A.y < B.y;
return A.x < B.x;
}
double CrossProduct ( 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 && CrossProduct ( Q[L-1], Q[L], v[i] ) <= 0 )
L--;
Q[++L] = v[i];
}
int l = L;
for ( int i = N; i >= 1; --i ){
while ( L > l && CrossProduct ( Q[L-1], Q[L], v[i] ) <= 0 )
L--;
Q[++L] = v[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, "%lf %lf\n", Q[i].x, Q[i].y );
return 0;
}