Pagini recente » Cod sursa (job #535429) | Cod sursa (job #85394) | Cod sursa (job #1973277) | Cod sursa (job #180377) | Cod sursa (job #2957980)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 120000;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
struct Point{
double x;
double y;
};
Point v[NMAX];
int n;
int findStartingPoint() {
int i, ind;
double miny, minx;
minx = miny = 1e9 + 1;
ind = -1;
for( i = 0; i < n; i++ ) {
if( v[i].y < miny ) {
ind = i;
miny = v[i].y;
minx = v[i].x;
}
else if( v[i].y == miny && v[i].x < minx ) {
ind = i;
minx = v[i].x;
}
}
return ind;
}
// orientation > 0 => invers trigonometric
// orientation < 0 => trigonometric
// orientation == 0 => coliniare
inline double orientation( Point a, Point b, Point c ) {
double compute;
compute = ( b.y - a.y ) * ( c.x - b.x ) - ( b.x - a.x ) * ( c.y - b.y );
return compute;
}
inline bool cmp( Point a, Point b ) {
return orientation( v[0], a, b ) <= 0;
}
vector <Point> convexHull;
void computeHull() {
int i;
convexHull.push_back( v[0] );
convexHull.push_back( v[1] );
for( i = 2; i < n; i++ ) {
while( convexHull.size() >= 2 && orientation( convexHull[convexHull.size()-2], convexHull[convexHull.size()-1], v[i] ) >= 0 )
convexHull.pop_back();
convexHull.push_back( v[i] );
}
}
int main() {
int i, ind;
fin >> n;
for( i = 0; i < n; i++ )
fin >> v[i].x >> v[i].y;
ind = findStartingPoint();
swap( v[0], v[ind] );
sort( v + 1, v + n, cmp );
computeHull();
fout << convexHull.size() << "\n";
fout << setprecision( 12 ) << fixed;
for( const Point& p: convexHull )
fout << p.x << " " << p.y << "\n";
return 0;
}