Pagini recente » Cod sursa (job #1645198) | Cod sursa (job #772274) | Cod sursa (job #1601432) | Cod sursa (job #795984) | Cod sursa (job #2744965)
#include <iostream>
#include <cstdio>
#include <fstream>
#include <deque>
#include <algorithm>
#include <iomanip>
using namespace std;
#define ld long double
#define x first
#define y second
const int NMAX = 12e4;
pair<ld, ld> v[NMAX];
deque <int> dq;
bool cmp( pair<ld,ld> a, pair<ld, ld> b ) {
return ( a.y - v[dq.front()].y ) * ( b.x - v[dq.front()].x ) >
( b.y - v[dq.front()].y ) * ( a.x - v[dq.front()].x );
}
bool cmp2( int i, int j ) {
return ( v[dq[i]].x - v[dq[i - 1]].x ) * ( v[j].y - v[dq[i - 1]].y ) >
( v[j].x - v[dq[i - 1]].x ) * ( v[dq[i]].y - v[dq[i - 1]].y );
}
int main() {
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
int n, i, minim = 0;
fin >> n;
for ( i = 0; i < n; i ++ ) {
fin >> v[i].x >> v[i].y;
if ( v[i].x <= v[minim].x ) {
minim = i;
}
}
swap( v[0], v[minim] );
dq.push_back( 0 );
sort( v + 1, v + n, cmp );
for ( i = 1; i < n; i ++ ) {
while ( dq.size() > 1 && cmp2( dq.size() - 1, i ) )
dq.pop_back();
dq.push_back( i );
}
fout << dq.size() << '\n';
for ( i = dq.size() - 1; i >= 0; i -- ) {
fout << fixed << setprecision( 12 ) << v[dq[i]].x << ' ' << v[dq[i]].y << '\n';
}
return 0;
}