Cod sursa(job #3301015)

Utilizator mcrg05Craciunescu Mihnea Gabriel mcrg05 Data 20 iunie 2025 19:45:54
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 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) { //prdus vectorial
    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);
    vector<Point> st;
    for (int i = 0; i < h; i++) { //parcurgem de la 0 la h - 1
        while (st.size() >= 2 && cross_product(st[st.size()-2], st[st.size()-1], points[i]) <= precizie) //verificam sa fie destule puncte in stiva, calculam produsul vectorial si comparam cu precizia
            st.pop_back();
        st.push_back(points[i]);
    }
    long long st_size = st.size();
    for (int i = h - 2; i >= 0; i--) { //parcurgem de la h - 2 la 0
        while (st.size() > st_size && cross_product(st[st.size()-2], st[st.size()-1], points[i]) <= precizie) //verificam sa fie destule puncte in stiva, calculam produsul vectorial si comparam cu precizia
            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(); //daca luam primul/ultimul punct de 2 ori
    cout << st.size() << '\n';
    cout << setprecision(6) << fixed;
    for (long long i = 0; i < st.size(); i++) {
        cout << st[i].x << ' ' << st[i].y << '\n';
    }
    return 0;
}