Pagini recente » Cod sursa (job #1324643) | Cod sursa (job #888488) | Cod sursa (job #1144314) | Cod sursa (job #1094737) | Cod sursa (job #2724850)
#include <iostream>
#include <cstdio>
#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;
}
bool egal( coord a, coord b ) {
return ( a.x == b.x && a.y == b.y );
}
double read_double(FILE *fin) {
char ch = fgetc(fin);
while (ch != '-' && ch != '.' && (ch < '0' || ch > '9'))
ch = fgetc(fin);
double sgn = 1;
if (ch == '-') {
sgn = -1;
ch = fgetc(fin);
}
double ans = 0;
while (ch >= '0' && ch <= '9') {
ans = ans * 10 + (ch - '0');
ch = fgetc(fin);
}
if (ch == '.') {
double p10 = 0.1;
ch = fgetc(fin);
while (ch >= '0' && ch <= '9') {
ans += p10 * ( ch - '0' );
p10 *= 0.1;
ch = fgetc(fin);
}
}
return ans * sgn;
}
int main() {
FILE *fin = fopen( "infasuratoare.in", "r" ), *fout = fopen( "infasuratoare.out", "w" );
int n, i, u, d;
fscanf(fin, "%d", &n);
// printf("%d\n", n); return 0;
for ( i = 0; i < n; i ++ ) {
v[i].x = read_double(fin);
v[i].y = read_double(fin);
// printf("%f %f\n", 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 ++;
}
}
fprintf( fout, "%d\n", d + u - egal( down[0], up[0] ) - egal( down[d - 1], up[u - 1] ) );
for ( i = 0; i < d - egal( down[d - 1], up[d - 1] ); i ++ )
fprintf( fout, "%.13f %.13f\n", down[i].x, down[i].y );
for ( i = u - 1; i >= 0 + egal( down[0], up[0] ); i -- )
fprintf( fout, "%.13f %.13f\n", up[i].x, up[i].y );
fclose( fin );
fclose( fout );
return 0;
}