Pagini recente » Cod sursa (job #2315046) | Cod sursa (job #1256993) | Cod sursa (job #893387) | Cod sursa (job #1256224) | Cod sursa (job #2724314)
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <iomanip>
using namespace std;
const int NMAX = 12e4;
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.x - a.x ) * ( b.y - a.y );
}
bool cmp1( coord a, coord b ) {
if ( a.x < b.x )
return 1;
if ( a.x == b.x )
return a.y < b.y;
return 0;
}
bool cmp2( coord a, coord b ) {
if ( a.x < b.x )
return 1;
if ( a.x == b.x )
return a.y > b.y;
return 0;
}
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, cmp1 );
u = d = 0;
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 ++;
}
}
sort( v, v + n, cmp2 );
for ( i = 0; i < n; i ++ ) {
if ( rel_pos( v[0], v[n - 1], v[i] ) >= v[i].y ) {
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 - 2 << '\n';
for ( i = 0; i < d - 1; i ++ )
fout << setprecision( 13 ) << down[i].x << ' ' << setprecision( 13 ) << down[i].y << '\n';
for ( i = u - 1; i >= 1; i -- )
fout << setprecision( 13 ) << up[i].x << ' ' << setprecision( 13 ) << up[i].y << '\n';
return 0;
}