Pagini recente » Cod sursa (job #846999) | Cod sursa (job #1795293) | Cod sursa (job #1988472) | Cod sursa (job #870316) | Cod sursa (job #3259829)
#include <stdio.h>
#include <vector>
#include <algorithm>
using ll = long long;
using ftype = double;
struct Point {
ftype x, y;
Point( ftype x, ftype y ): 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;
}
std::vector<Point> hull_half( const std::vector<Point> &points, int sgn ){
std::vector<Point> ret;
for( Point P : points ){
while( ret.size() >= 2 && sdet( ret.end()[-2], ret.end()[-1], P ) * sgn > 0 )
ret.pop_back();
ret.push_back( P );
}
return ret;
}
std::vector<Point> hull( std::vector<Point> &points ) {
std::sort( points.begin(), points.end(), []( const Point &a, const Point &b ) -> bool {
if( a.x == b.x )
return a.y < b.y;
return a.x < b.x;
} );
std::vector<Point> ret1 = hull_half( points, +1 );
std::vector<Point> ret2 = hull_half( points, -1 );
ret1.insert( ret1.end(), ret2.rbegin() + 1, ret2.rend() - 1 );
return ret1;
}
int main() {
FILE *fin = fopen( "infasuratoare.in", "r" );
FILE *fout = fopen( "infasuratoare.out", "w" );
int n;
fscanf( fin, "%d", &n );
std::vector<Point> 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, "%.6lf %.6lf\n", P.x, P.y );
fclose( fin );
fclose( fout );
return 0;
}