Cod sursa(job #3366830)

Utilizator prodsevenStefan Albu prodseven Data 4 octombrie 2026 16:06:00
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct Punct {
    long double x, y;
    friend bool operator<(Punct a, Punct b) {
        if(a.x < b.x)
            return true;
        if(a.x == b.x && a.y < b.y)
            return true;
        return false;
    }
};

int n;
vector<Punct> puncte;
vector<Punct> st;

inline long double ccw(Punct o, Punct a, Punct b)
{
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

inline bool cmp(Punct a, Punct b) {
    return ccw(puncte[0], a, b) < 0;
}

int main() {
    cin >> n;
    for (int i = 0 ; i < n ; ++i) {
        long double x, y;
        cin >> x >> y;
        puncte.push_back({x, y});
    }
    // pozitia celui mai stanga-jos punct
    int pos = 0;
    for (int i = 1 ; i < n ; ++i) {
        if (puncte[i] < puncte[pos]) pos = i;
    }
    // il punem pe pozitia 0
    swap(puncte[0], puncte[pos]);
    // sortam dupa unghiuri fara el
    sort(puncte.begin() + 1, puncte.end(), cmp);
    // cat timp punctul de vrem sa-l adaugam cauzeaza poligonul sa fie concav, scoatem ultimul punct din infasurare
    st.push_back(puncte[0]);
    st.push_back(puncte[1]);
    for (int i = 2 ; i < n ; ++i) {
        // cat timp putem scoate si se face concav
        while (st.size() >= 2 && ccw(st[st.size() - 2], st[st.size() - 1], puncte[i]) > 0) {
            st.pop_back();
        }
        st.push_back(puncte[i]);
    }
    cout << st.size() << "\n";
    for (int i = st.size() - 1 ; i >= 0 ; --i) {
        cout << fixed << setprecision(6) << st[i].x << " " << st[i].y << "\n";
    }
    return 0;
}