Pagini recente » Cod sursa (job #2656727) | Cod sursa (job #812286) | Cod sursa (job #2323377) | Cod sursa (job #247826) | Cod sursa (job #2741577)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
const int MaxN = 120001;
struct point {
double x, y;
} p[MaxN];
inline int det( point a, point b, point c ) {
return (a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - a.x * c.y - c.x * b.y);
}
struct cmp_point {
bool operator () ( const point &a, const point &b ) {
return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}
};
struct cmp_ang {
bool operator () ( const point &a, const point &b ) {
return det( p[0], a, b ) > 0;
}
};
int s[MaxN];
int sp;
int main() {
int n, ind;
fin >> n;
for ( int i = 0; i < n; ++i ) {
fin >> p[i].x >> p[i].y;
}
sort( p, p + n, cmp_point() );
sort( p, p + n, cmp_ang() );
s[sp++] = 0;
s[sp++] = 1;
ind = 2;
while ( ind < n ) {
while ( sp > 1 && det( p[s[sp - 1]], p[s[sp - 2]], p[ind] ) > 0 ) {
--sp;
}
s[sp++] = ind++;
}
fout << sp << "\n";
fout << fixed << setprecision( 6 );
for ( int i = 0; i < sp; ++i ) {
fout << p[s[i]].x << " " << p[s[i]].y << "\n";
}
fin.close();
fout.close();
return 0;
}