Pagini recente » Cod sursa (job #2847810) | Cod sursa (job #265043) | Cod sursa (job #2323204) | Cod sursa (job #119406) | Cod sursa (job #3226627)
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pll pair<long long, long long>
using ll = long long;
const int VALMAX = 1e6 + 1e3;
const int LOGMAX = 18;
const int INF = 1e9;
const int NMAX = 120e3 + 1;
const double EPS = 0.000005;
const int IDK = 1e6 * 20 + 5;
mt19937 rnd( chrono::steady_clock::now().time_since_epoch().count() );
//#ifndef HOME
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
#define cin fin
#define cout fout
//#endif // HOME
struct Point{
double x, y;
};
Point points[NMAX];
vector<Point> st;
int n;
// < 0 => trigonometric
// > 0 => invers trigonometric
// = 0 => coliniare
double orientation( Point a, Point b, Point c ) {
return ( b.y - a.y ) * ( c.x - b.x ) - ( b.x - a.x ) * ( c.y - b.y );
}
void construct( int semn, vector<Point>&ans ) {
int i;
st.clear();
st.push_back( points[0] );
for( i = 1; i < n; i++ ) {
while( st.size() >= 2 && orientation( st.end()[-2], st.end()[-1], points[i] ) * semn <= 0 )
st.pop_back();
st.push_back( points[i] );
}
for( i = 1; i < st.size() - 1; i++ )
ans.push_back( st[i] );
}
vector <Point> top;
vector <Point> bottom;
void solve() {
int i;
cin >> n;
for( i = 0; i < n; i++ )
cin >> points[i].x >> points[i].y;
sort( points, points + n, []( Point& a, Point& b ) {
return a.x < b.x || ( a.x == b.x && a.y > b.y );
} );
Point first = points[0];
Point last = points[n-1];
construct( 1, top );
construct( -1, bottom );
cout << fixed << setprecision( 12 );
cout << 2 + top.size() + bottom.size() << "\n";
cout << first.x << " " << first.y << "\n";
for( auto p: bottom )
cout << p.x << " " << p.y << "\n";
cout << last.x << " " << last.y << "\n";
reverse( top.begin(), top.end() );
for( auto p: top )
cout << p.x << " " << p.y << "\n";
}
int main() {
//ios_base::sync_with_stdio( false );
//cin.tie( NULL );
//cout.tie( NULL );
int t = 1;
// cin >> t;
while( t-- )
solve();
}