Cod sursa(job #3197610)

Utilizator vlad_binVlad Bintintan vlad_bin Data 27 ianuarie 2024 10:52:23
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;
using punct = pair<long double, long double>;

double det(const punct& a, const punct& b, const punct& c) {
    return a.first * b.second
        + b.first * c.second
        + a.second * c.first
        - b.second * c.first
        - a.second * b.first
        - c.second * a.first;
}

int main() {
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    int n;
    in >> n;

    vector<punct> points(n);

    for (auto& point : points)
        in >> point.first >> point.second;

    auto left_point = ranges::min_element(points, {}, &punct::first);

    iter_swap(points.begin(), left_point);

    sort(next(points.begin()), points.end(), 
        [&points](const punct& a, const punct& b) {
            return det(points.front(), a, b) >= 0;
        } );

    vector<punct> st(n);
    int index = 0;
    st[index] = points.front();

    for (int i = 1; i < n; i++) {
        while (index > 0 && det(st[index-1], st[index], points[i]) >= 0)
            index--;
        st[index++] = points[i];
    }

    out << index + 1 << '\n';
    out << setprecision(6);
    for (auto point : st | views::take(index))
        out << point.first << ' ' << point.second << '\n';

    out << points.front().first << ' ' << points.front().second << endl;
}