Pagini recente » Cod sursa (job #3269559) | Cod sursa (job #953204) | Cod sursa (job #2870381) | Cod sursa (job #3265398) | Cod sursa (job #3226438)
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
int n, p;
vector<pair<double, double>> points;
double determinant(const pair<double, double>& p,
const pair<double, double>& q,
const pair<double, double>& r) {
return (q.first * r.second + p.first * q.second + r.first * p.second) -
(q.first * p.second + p.first * r.second + r.first * q.second);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
cin >> n;
for (int i = 0;i < n;++i) {
double x, y;
cin >> x >> y;
points.push_back({x, y});
}
p = 0;
for (int i = 1;i < n;++i) {
if (points[i] < points[p])
p = i;
}
swap(points[0], points[p]);
sort(points.begin() + 1, points.end(), [&](const pair<double, double>& a, const pair<double, double>& b) {
return determinant(points[0], a, b) > 0;
});
vector<pair<double, double>> hull;
hull.push_back(points[0]);
hull.push_back(points[1]);
for (int i = 2;i < n; ++i) {
while(hull.size() >= 2 && determinant(hull[hull.size() - 2], hull[hull.size() - 1], points[i]) <= 0)
hull.pop_back();
hull.push_back(points[i]);
}
cout << hull.size() << "\n";
for (const auto& point : hull)
cout << setprecision(9) << point.first << ' ' << point.second << '\n';
return 0;
}