Pagini recente » Cod sursa (job #3291764) | Cod sursa (job #2854219) | Cod sursa (job #383455) | Cod sursa (job #28703) | Cod sursa (job #3194039)
#include <stdio.h>
#include <algorithm>
#include <vector>
using ftype = double;
struct Point {
ftype x, y;
Point( ftype x = 0, ftype y = 0 ): x( x ), y( y ) {}
};
int sdet( const Point& a, const Point& b, const Point& c ) {
ftype det = (a.x - b.x) * (a.y - c.y) - (a.y - b.y) * (a.x - c.x);
if( det < 0 )
return -1;
if( det > 0 )
return +1;
return 0;
}
using vp = std::vector<Point>;
vp hull_half( const vp& points, int sgn ) {
vp ret;
for( Point p : points ){
while( (int)ret.size() >= 2 && sgn * sdet( ret.end()[-2], ret.end()[-1], p ) < 0 )
ret.pop_back();
ret.push_back( p );
}
return ret;
}
vp hull( vp points ) {
std::sort( points.begin(), points.end(), []( const Point &a, const Point &b ) -> bool {
if( a.x != b.x )
return a.x < b.x;
return a.y < b.y;
} );
vp ret = hull_half( points, +1 );
vp ret2 = hull_half( points, -1 );
ret.insert( ret.end(), ret2.rbegin() + 1, ret2.rend() - 1 );
return ret;
}
int main() {
FILE *fin = fopen( "infasuratoare.in", "r" );
FILE *fout = fopen( "infasuratoare.out", "w" );
int n;
fscanf( fin, "%d", &n );
vp v;
for( int i = 0 ; i < n ; i++ ){
ftype x, y;
fscanf( fin, "%lf%lf", &x, &y );
v.emplace_back( x, y );
}
v = hull( v );
fprintf( fout, "%d\n", (int)v.size() );
for( Point p : v )
fprintf( fout, "%lf %lf\n", p.x, p.y );
fclose( fin );
fclose( fout );
return 0;
}