Cod sursa(job #3357831)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 15:25:13
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#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;
}