Pagini recente » Cod sursa (job #2601891) | Cod sursa (job #2151709) | Cod sursa (job #2901317) | Cod sursa (job #1186389) | Cod sursa (job #2724274)
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <iomanip>
using namespace std;
const int NMAX = 1e5;
struct coord {
double x;
double y;
} v[NMAX];
deque <coord> up;
deque <coord> down;
double rel_pos( coord a, coord b, coord c ) {
return a.y + (c.x - a.x) * ( b.y - a.y ) / ( b.x - a.x );
}
bool cmp( coord a, coord b ) {
return a.x < b.x;
}
int main() {
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
int n, i, u, d;
fin >> n;
for ( i = 0; i < n; i ++ ) {
fin >> v[i].x >> v[i].y;
}
sort( v, v + n, cmp );
u = d = 0;
///cout << v[0].x << ' ' << v[0].y << endl << v[n-1].x << ' ' << v[n-1].y;
for ( i = 0; i < n; i ++ ) {
if ( rel_pos( v[0], v[n - 1], v[i] ) <= v[i].y ) {
while ( u > 1 && rel_pos( up[u - 2], v[i], up[u - 1] ) >= up[u - 1].y ) {
up.pop_back();
u --;
}
up.push_back( v[i] );
u ++;
} else {
while ( d > 1 && rel_pos( down[d - 2], v[i], down[d - 1] ) <= down[d - 1].y ) {
down.pop_back();
d --;
}
down.push_back( v[i] );
d ++;
}
}
fout << d + u << '\n';
for ( i = 0; i < u; i ++ )
fout << setprecision( 13 ) << up[i].x << ' ' << setprecision( 13 ) << up[i].y << '\n';
for ( i = d - 1; i >= 0; i -- )
fout << setprecision( 13 ) << down[i].x << ' ' << setprecision( 13 ) << down[i].y << '\n';
return 0;
}