Cod sursa(job #3138792)

Utilizator AndreiPaval03Andrei Paval AndreiPaval03 Data 22 iunie 2023 13:21:24
Problema Infasuratoare convexa Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
#include <iomanip>

double product(
    std::pair<double, double> p0, 
    std::pair<double, double> p1, std::pair<double, double> p2
) {
    return (p1.first - p0.first) * (p2.second - p0.second) - (p2.first - p0.first) * (p1.second - p0.second);
}

double x;
double y;

int main() {
    std::ifstream cin("infasuratoare.in");
    std::ofstream cout("infasuratoare.out");

    int n; cin >> n;
    std::vector<std::pair<double, double>> points(n);
    for (int i = 0; i < n; ++i) {
        double x; cin >> x;
        double y; cin >> y;
        points[i] = std::make_pair(x, y);
    }

    int k = 0;
    for (int i = 1; i < n; ++i) {
        if (points[i] < points[k]) {
            k = i;
        }
    }
    std::swap(points[k], points[0]);
    x = points[0].first;
    y = points[1].second;
    sort(
        points.begin() + 1, 
        points.end(), 
        [](auto a, auto b) {
            return product(std::make_pair(x, y), a, b) < 0;
        }
    );

    std::vector<int> st(n);
    int head = 1;
    st[0] = 0;
    st[1] = 1;
    for (int i = 2; i < n; ++i) {
        while (
            head >= 1 && 
            product(points[st[head - 1]], points[st[head]], points[i]) > 0
        ) {
            --head;
        }
        st[++head] = i;
    }

    cout << head + 1 << "\n";
    for (int i = head; i >= 0; --i) {
        cout << std::setprecision(9) << points[st[i]].first << " " << points[st[i]].second << '\n';
    }


    return 0;
}