Pagini recente » Cod sursa (job #1409124) | Cod sursa (job #2854864) | Cod sursa (job #1658740) | Cod sursa (job #1693418) | Cod sursa (job #3351869)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
struct Point {
long double x, y;
};
bool operator == (Point a, Point b) {
return a.x == b.x && a.y == b.y;
}
double 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> HullHalf(vector<Point> pts, int z) {
vector<Point> stk;
for (auto p : pts) {
while (stk.size() >= 2 && z * det(stk[stk.size() - 2], stk.back(), p) < 0) stk.pop_back();
stk.push_back(p);
}
return stk;
}
vector<Point> convexhull(vector<Point> pts) {
sort(pts.begin(), pts.end(), [&](Point a, Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y); });
pts.resize(unique(pts.begin(), pts.end()) - pts.begin());
vector<Point> up = HullHalf(pts, +1), low = HullHalf(pts, -1);
up.insert(up.end(), low.rbegin() + 1, low.rend() - 1);
return up;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
cout << setprecision(10) << fixed;
int n; cin >> n;
vector<Point> pts(n);
for (auto &x : pts) cin >> x.x >> x.y;
auto ch = convexhull(pts);
cout << ch.size() << "\n";
for (auto [x, y] : ch) {
cout << x << " " << y << "\n";
}
return 0;
}