Pagini recente » Cod sursa (job #2140862) | Cod sursa (job #1072965) | Cod sursa (job #321017) | Cod sursa (job #615349) | Cod sursa (job #2889865)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define pi pair<ll, ll>
#define sz(x) (int)((x).size())
#define all(a) (a).begin(), (a).end()
/*const ll maxn = 1e5;
int f[maxn],nf[maxn],inv[maxn];
const int M=998244353;
void init(){
inv[1]=1; for (int i=2;i<maxn;i++) inv[i]=M-1ll*(M/i)*inv[M%i]%M;
f[0]=nf[0]=1; for (int i=1;i<maxn;i++) f[i]=1ll*f[i-1]*i%M,nf[i]=1ll*nf[i-1]*inv[i]%M;
}
int C(int x,int y){return 1ll*f[x]*nf[y]%M*nf[x-y]%M;} */
const ll mod = 1e9+7;
ll n, k, m, mi, ma;
const ll N = 2e5;
typedef pair<double, double> point;
vector<point> v(N), a(N);
double cross_product(point a, point b, point c){
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
bool cmp(point p1, point p2){
return cross_product(v[0], p1, p2) < 0;
}
void sort_points(){
ll pos = 0;
for(int i = 1; i<n; i++) if(v[i] < v[pos]) pos = i;
swap(v[0], v[pos]);
sort(v.begin() + 1, v.begin() + n, cmp);
}
void solve(){
cin >> n;
for(int i = 0; i<n; i++){
cin >> v[i].x >> v[i].y;
}
sort_points();
point a[n + 5];
ll head = 1;
a[0] = v[0];
a[1] = v[1];
for(int i = 2; i<n; i++){
while(head >= 1 && cross_product(a[head - 1], a[head], v[i]) > 0) head--;
a[++head] = v[i];
}
cout << head << "\n";
for(int i = head; i>=0; i--){
cout << setprecision(9) << fixed << a[i].x << " " << a[i].y << "\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//init();
int t=1;
//cin >> t;
while(t--) solve();
return 0;
}