Pagini recente » Cod sursa (job #3341113) | Cod sursa (job #1053673) | Cod sursa (job #2254468) | Cod sursa (job #1050443) | Cod sursa (job #3346323)
#include <bits/stdc++.h>
using namespace std;
struct Point {
double x, y;
};
double cross(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
cin >> n;
vector<Point> p(n);
for (int i = 0; i < n; i++)
cin >> p[i].x >> p[i].y;
sort(p.begin(), p.end(), [](Point a, Point b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
});
vector<Point> hull;
for (int i = 0; i < n; i++) {
while (hull.size() >= 2 &&
cross(hull[hull.size()-2], hull[hull.size()-1], p[i]) <= 0)
hull.pop_back();
hull.push_back(p[i]);
}
int t = hull.size() + 1;
for (int i = n-2; i >= 0; i--) {
while (hull.size() >= t &&
cross(hull[hull.size()-2], hull[hull.size()-1], p[i]) <= 0)
hull.pop_back();
hull.push_back(p[i]);
}
hull.pop_back();
cout << hull.size() << "\n";
cout << fixed << setprecision(6);
for (auto &pt : hull)
cout << pt.x << " " << pt.y << "\n";
return 0;
}