Pagini recente » Cod sursa (job #2942154) | Cod sursa (job #1776134) | Cod sursa (job #709414) | Cod sursa (job #2392139) | Cod sursa (job #3221114)
#include <bits/stdc++.h>
using namespace std;
#define dd double
#define point complex<dd>
#define x real()
#define y imag()
const int N = 120009;
int dot_product(point a, point b){return (conj(a) * b).x;}
int cross_product(point a, point b){return (conj(a) * b).y;}
int n, sz;
point v[N], stk[N];
signed main()
{
cin >> n;
double a, b;
for(int i = 1; i <= n; ++i)
{
cin >> a >> b;
v[i] = a + b * 1i;
}
int p = 1;
for(int i = 2; i <= n; ++i)
if(v[i].x < v[p].x || (v[i].x == v[p].x && v[i].y > v[p].y))
p = i;
swap(v[1], v[p]);
sort(v + 2, v + n + 1, [&](point a, point b){return cross_product(a - v[1], b - v[1]) < 0;});
stk[++sz] = v[1];
for(int i = 2; i <= n; ++i)
{
while(sz >= 2 && cross_product(stk[sz] - stk[sz - 1], v[i] - stk[sz - 1]) > 0)sz --;
stk[++ sz] = v[i];
}
cout << sz << '\n';
cout << fixed << setprecision(6);
for(int i = 1; i <= sz; ++i)cout << stk[i].x << ' ' << stk[i].y << '\n';
return 0;
}