Pagini recente » Cod sursa (job #2390620) | Borderou de evaluare (job #508712) | Cod sursa (job #2251373) | Cod sursa (job #327757) | Cod sursa (job #2953602)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
ifstream cin( "infasuratoare.in" );
ofstream cout( "infasuratoare.out" );
struct points {
double x, y;
};
vector<points> rez;
points v[ 120000 ];
int n, minn;
inline double isClockwise( const points& a, const points& b, const points& c ) {
return ( b.y - a.y ) * ( c.x - b.x ) - ( b.x - a.x ) * ( c.y - b.y );
}
void infasurare() {
rez.push_back( v[ 0 ] );
rez.push_back( v[ 1 ] );
for( int i = 2; i < n; ++i ) {
while( isClockwise( rez[ rez.size() - 2 ], rez.back(), v[ i ] ) >= 0 )
rez.pop_back();
rez.push_back( v[ i ] );
}
}
int main()
{
cin >> n;
for( int i = 0; i < n; ++i ) {
cin >> v[ i ].x >> v[ i ].y;
if( v[ i ].y < v[ minn ].y )
minn = i;
}
swap( v[ 0 ], v[ minn ] );
sort( v + 1, v + n, []( const points& a, const points& b ) {
return isClockwise( v[ 0 ], a, b ) < 0;
} );
infasurare();
cout << rez.size() << '\n';
cout << fixed << std::setprecision(9);
for( const points& p : rez )
cout << p.x << ' ' << p.y << '\n';
return 0;
}