Pagini recente » Cod sursa (job #2506159) | Cod sursa (job #2239703) | Cod sursa (job #903211) | Cod sursa (job #623131) | Cod sursa (job #1671267)
# include <cstdio>
# include <algorithm>
# define N 120000
# define EPS 0.00000001
using namespace std;
struct coord {
double x, y;
} v[N], s[N];
inline double ang( struct coord a, struct coord b ) {
return ( a.y - s[0].y ) * ( b.x - s[0].x ) > ( b.y - s[0].y ) * ( a.x - s[0].x );
}
inline int verif( int i, int j )
{
double a=(s[i].y-s[i-1].y)*(v[j].x-s[i-1].x);
double b=(v[j].y-s[i-1].y)*(s[i].x-s[i-1].x);
return a<b;
}
int main() {
FILE *fin = fopen( "infasuratoare.in", "r" ), *fout = fopen( "infasuratoare.out", "w" );
int n, i, vf, l;
fscanf( fin, "%d", &n );
for ( i = 0; i < n; i ++ )
fscanf( fin, "%lf%lf", &v[i].x, &v[i].y );
s[0] = v[0];
for ( i = 1; i < n; i ++ )
if ( v[i].x < s[0].x ) {
s[0] = v[i];
l = i;
}
swap( v[l], v[0] );
sort( v + 1, v + n, ang );
vf = -1;
for ( i = 0; i < n; i ++ ) {
while ( vf > 1 && verif(vf, i) /* v[i].y - s[vf - 1].y ) * ( s[vf].x - s[vf - 1].x ) > ( s[vf].y - s[vf - 1].y ) * ( v[i].x - s[vf - 1].x )*/ )
vf --;
s[++ vf] = v[i];
}
fprintf( fout, "%d\n", vf );
for ( i = vf; i >= 0; i -- )
fprintf( fout, "%lf %lf\n", s[i].x, s[i].y );
fclose( fin );
fclose( fout );
return 0;
}