Pagini recente » Cod sursa (job #3302333) | Cod sursa (job #3314172) | Cod sursa (job #3325047)
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct Point {
ld x;
ld y;
};
ld det(Point a, Point b, Point c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
vector<Point> hull(vector<Point> pts) {
for (auto &p : pts) {
if (p.x < pts[0].x || (p.x == pts[0].x && p.y < pts[0].y)) {
swap(p, pts[0]);
}
}
sort(pts.begin() + 1, pts.end(), [&](Point a, Point b) {
return det(pts[0], a, b) > 0;
});
vector<Point> stk;
stk.push_back(pts[0]);
stk.push_back(pts[1]);
for (int i = 2; i < pts.size(); ++i) {
while (stk.size() >= 2 && det(stk[stk.size() - 2], stk.back(), pts[i]) < 0) {
stk.pop_back();
}
stk.push_back(pts[i]);
}
return stk;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
cin >> n;
vector<Point> pts(n);
for (auto &p : pts) cin >> p.x >> p.y;
vector<Point> ch = hull(pts);
cout << ch.size() << "\n";
cout << setprecision(10) << fixed;
for (auto p : ch) cout << p.x << " " << p.y << "\n";
return 0;
}