Pagini recente » Cod sursa (job #2027491) | Cod sursa (job #1200984) | Cod sursa (job #193296) | Cod sursa (job #2536250) | Cod sursa (job #3193865)
#include <stdio.h>
#include <vector>
#include <algorithm>
using ll = long long;
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;
}
std::vector<Point> hull_half( const std::vector<Point> points, int sgn ) {
std::vector<Point> 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;
}
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.x < b.x;
return a.y < b.y;
} );
std::vector<Point> ret = hull_half( points, +1 );
std::vector<Point> 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 );
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, "%lf %lf\n", p.x, p.y );
fclose( fin );
fclose( fout );
}