Pagini recente » Cod sursa (job #2535676) | Cod sursa (job #2358537) | Cod sursa (job #2702070) | Cod sursa (job #2757849) | Cod sursa (job #2702819)
#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];
struct angs {
double val;
int ind;
} ang[MaxN];
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 angs &a, const angs &b ) {
return a.val < b.val;
}
};
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 > 0);
}
int order[MaxN];
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() );
for ( int i = 1; i < n; ++i ) {
ang[i - 1].val = atan2( p[i].y - p[0].y, p[i].x - p[0].x );
ang[i - 1].ind = i;
}
sort( ang, ang + n - 1, cmp_ang() );
order[0] = 0;
for ( int i = 0; i < n - 1; ++i ) {
order[i + 1] = ang[i].ind;
}
s[sp++] = order[0];
s[sp++] = order[1];
ind = 2;
while ( ind < n ) {
while ( sp > 1 && det( p[s[sp - 1]], p[s[sp - 2]], p[order[ind]] ) ) {
--sp;
}
s[sp++] = order[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;
}