Pagini recente » Cod sursa (job #505730) | Cod sursa (job #1321282) | Cod sursa (job #1322588) | Cod sursa (job #1320584) | Cod sursa (job #3357831)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
pair<double, double> A[120005];
int under[120005];
int top[120005];
bool used[120005];
long long det(pair<long long, long long> a, pair<long long, long long> b, pair<long long, long long> c) {
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
int main() {
int n;
cin >> n;
vector<pair<long long, long long>> points(n);
for (int i = 0; i < n; i++) {
double x, y;
cin >> x >> y;
points[i] = {round(x * 10000), round(y * 10000)};
}
sort(points.begin(), points.end(), [](const pair<long long, long long>& a, const pair<long long, long long>& b) {
return a.first < b.first || (a.first == b.first && a.second < b.second);
});
int k = 0;
for (int i = 0; i < n; i++) {
while (k >= 2 && det(points[under[k-2]], points[under[k-1]], points[i]) <= 0) k--;
under[k++] = i;
}
int t = k;
for (int i = n - 2; i >= 0; i--) {
while (k >= t + 2 && det(points[top[k-2]], points[top[k-1]], points[i]) <= 0) k--;
top[k++] = i;
}
k--;
cout << k << '\n';
vector<bool> used(n, false);
for (int i = 0; i < k; i++) {
int idx = (i < t) ? under[i] : top[i];
used[idx] = true;
}
vector<pair<long long, long long>> hull;
for (int i = 0; i < k; i++) {
int idx = (i < t) ? under[i] : top[i];
hull.push_back(points[idx]);
}
sort(hull.begin(), hull.end());
hull.erase(unique(hull.begin(), hull.end()), hull.end());
cout << hull.size() << '\n';
for (auto& p : hull) {
cout << fixed << setprecision(5) << (double)p.first / 10000.0 << " " << (double)p.second / 10000.0 << '\n';
}
return 0;
}