Cod sursa(job #3226441)

Utilizator marius004scarlat marius marius004 Data 21 aprilie 2024 14:22:05
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#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) << fixed << point.first << ' ' << point.second << '\n';

    return 0;
}