Pagini recente » Cod sursa (job #3127553) | Cod sursa (job #214915) | Cod sursa (job #1506836) | Cod sursa (job #382115) | Cod sursa (job #2030759)
#include <bits/stdc++.h>
using namespace std;
struct psychotronic_induction {
int electromagnetic_wave = 7;
};
const int inf = 0x3f3f3f3f;
const long long infL = LLONG_MAX;
const int nmax = 1e5 + 10;
int n;
pair < double, double > a[nmax];
int st[nmax], st_size;
void input() {
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i].first >> a[i].second;
}
bool sign_(int x, int y, int z) {
double curr = a[x].first * (a[y].second - a[z].second) + a[y].first * (a[z].second - a[x].second) + a[z].first * (a[x].second - a[y].second);
return curr > 0;
}
void convex_hull() {
sort(a + 1, a + n + 1);
st[++st_size] = 1;
for (int i = 2; i <= n; ++i) {
while (st_size > 1 && sign_(st[st_size-1], st[st_size], i))
st_size--;
st[++st_size] = i;
}
for (int i = n - 1; i; --i) {
while (st_size > 1 && sign_(st[st_size-1], st[st_size], i))
st_size--;
st[++st_size] = i;
}
st_size--;
reverse(st + 1, st + st_size + 1);
}
void output() {
cout << st_size << '\n';
cout << fixed << setprecision(6);
for (int i = 1; i <= st_size; ++i)
cout << a[st[i]].first << ' ' << a[st[i]].second << '\n';
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
ios_base :: sync_with_stdio(false);
input();
convex_hull();
output();
return 0;
}