Pagini recente » Cod sursa (job #1156167) | Cod sursa (job #379934) | Cod sursa (job #2874665) | Cod sursa (job #15918) | Cod sursa (job #2724253)
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;
const int NMAX = 1e5;
struct coord {
double x;
double y;
} v[NMAX];
deque <coord> ans[2];
bool rel_pos( coord a, coord b, coord c, int dir ) {
double cy = a.y + (c.x - a.x) * ( b.y - a.y ) / ( b.x - a.x );
if ( dir == 1 ) {
return c.y >= cy;
}
return c.y <= cy;
}
void add( coord a, int dir ) { /// 1 - up
while ( ans[dir].size() > 1 && !rel_pos( ans[dir][ans[dir].size() - 2], a, ans[dir].back(), dir ) ) {
ans[dir].pop_back();
}
ans[dir].push_back( a );
}
bool cmp( coord a, coord b ) {
return a.x < b.x;
}
int main() {
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
int n, i;
fin >> n;
for ( i = 0; i < n; i ++ ) {
fin >> v[i].x >> v[i].y;
}
sort( v, v + n, cmp );
ans[0].push_back( v[n - 1] );
ans[1].push_back( v[0] );
///cout << v[0].x << ' ' << v[0].y << endl << v[n-1].x << ' ' << v[n-1].y;
for ( i = 1; i < n - 1; i ++ ) {
if ( rel_pos( v[0], v[n - 1], v[i], 1 ) == 1 )
add( v[i], 1 );
}
for ( i = n - 1; i >= 1; i -- ) {
if ( rel_pos( v[0], v[n - 1], v[i], 1 ) == 0 )
add( v[i], 0 );
}
fout << ans[1].size() + ans[0].size() << '\n';
for ( int j = 1; j >= 0; j -- ) {
for ( i = 0; i < ans[j].size(); i ++ )
fout << ans[j][i].x << ' ' << ans[j][i].y << '\n';
}
return 0;
}