Pagini recente » Cod sursa (job #76552) | Cod sursa (job #3297537) | Cod sursa (job #3297525) | Cod sursa (job #3297339)
#include <stdio.h>
#include <vector>
#include <algorithm>
using ftype = long double;
struct Point {
ftype x, y;
bool operator < ( const Point& that ) const {
if( x != that.x )
return x < that.x;
return y < that.y;
}
};
constexpr ftype EPS = 1e-9;
int sgn( ftype x ) { return (x > EPS) - (x < -EPS); }
int sdet( Point A, Point B, Point C ) {
ftype det = (A.x - B.x) * (A.y - C.y) - (A.y - B.y) * (A.x - C.x);
return sgn(det);
}
std::vector<Point> hull_half( const std::vector<Point> &v, int sgn ){
std::vector<Point> ret;
for( Point P : v ){
while( (int)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> v ){
std::sort( v.begin(), v.end() );
std::vector<Point> ret1 = hull_half( v, +1 );
std::vector<Point> ret2 = hull_half( v, -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.push_back({ x, y });
}
v = hull( v );
fprintf( fout, "%d\n", (int)v.size() );
for( auto [x, y]: v )
fprintf( fout, "%.6Lf, %.6Lf\n", x, y );
fclose( fin );
fclose( fout );
return 0;
}