Cod sursa(job #3301016)

Utilizator mcrg05Craciunescu Mihnea Gabriel mcrg05 Data 20 iunie 2025 19:49:10
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
using namespace std;

#define precizie 1e-12

struct Point {
    double x, y;
};

bool comp(const Point& A, const Point& B) {
    if (fabs(A.x - B.x) > precizie)
        return A.x < B.x;
    return A.y < B.y;
}

double cross_product(const Point& O, const Point& A, const Point& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

int main() {
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int h;
    cin >> h;
    vector<Point> points(h);
    for (int i = 0; i < h; i++) {
        cin >> points[i].x >> points[i].y;
    }
    sort(points.begin(), points.end(), comp);
    // Elimină duplicatele
    points.erase(unique(points.begin(), points.end(), [](const Point& a, const Point& b) {
        return fabs(a.x - b.x) < precizie && fabs(a.y - b.y) < precizie;
    }), points.end());
    h = points.size();

    vector<Point> st;
    for (int i = 0; i < h; i++) {
        while (st.size() >= 2 && cross_product(st[st.size()-2], st[st.size()-1], points[i]) <= precizie)
            st.pop_back();
        st.push_back(points[i]);
    }
    size_t st_size = st.size();
    for (int i = h - 2; i >= 0; i--) {
        while (st.size() > st_size && cross_product(st[st.size()-2], st[st.size()-1], points[i]) <= precizie)
            st.pop_back();
        st.push_back(points[i]);
    }
    if (st.size() > 1 && fabs(st.front().x - st.back().x) < precizie && fabs(st.front().y - st.back().y) < precizie)
        st.pop_back();
    cout << st.size() << '\n';
    cout << setprecision(6) << fixed;
    for (size_t i = 0; i < st.size(); i++) {
        cout << st[i].x << ' ' << st[i].y << '\n';
    }
    return 0;
}