Pagini recente » Cod sursa (job #50284) | Cod sursa (job #2583457) | Cod sursa (job #1043901) | Cod sursa (job #1082621) | Cod sursa (job #2410220)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 2e4 + 10;
struct p{
long double x, y;
p(long double _x = 0, long double _y = 0) : x(_x), y(_y) {}
const bool operator < (const p &o) const {
if(x == o.x) return y < o.y;
return x < o.x;
}
}v[MAXN], stk[MAXN];
int stkSize = 0;
long double det(p a, p b, p c) {
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
int main() {
#ifdef BLAT
freopen("input", "r", stdin);
#else
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; ++i) {
cin >> v[i].x >> v[i].y;
if(v[i] < v[0]) swap(v[i], v[0]);
}
sort(v + 1, v + n, [&](p &a, p &b) -> bool {
return det(v[0], a, b) < 0;
});
v[n] = v[0];
stkSize = 0;
for(int i = 0; i <= n; ++i) {
while(stkSize >= 2 && det(stk[stkSize-1], stk[stkSize], v[i]) >= 0) {
stkSize --;
}
stk[++stkSize] = v[i];
}
cout << stkSize - 1 << '\n';
for(int i = 1; i <= stkSize - 1; ++i) {
cout << setprecision(12) << fixed << stk[i].x << ' ' << stk[i].y << '\n';
}
return 0;
}