Cod sursa(job #3345593)

Utilizator amalia_ghicaAmalia Ghica amalia_ghica Data 10 martie 2026 10:40:22
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.2 kb
#include <bits/stdc++.h>

using namespace std;
struct jd{
    double l, c;
};
jd v[120005];
vector<jd> slope;
bool cmp(jd a, jd b){
    if(a.l <= 0  &&  b.l >= 0){
        return a.l < b.l;
    }else if(b.l <= 0  &&  a.l >= 0){
        return a.l < b.l;
    }

    return a.l > b.l;
}
bool trigo(jd x, jd y, jd z){
    double res;
    res = x.l * y.c - x.c * y.l + y.l * z.c - y.c * z.l + z.l * x.c - z.c * x.l;
    return res > 0;
}
vector<double> st;
int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    double n, x, y, mx = 1000000001, my = 1000000001, prim;
    int j;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x >> y;
        v[i].l = x;
        v[i].c = y;
        if(my > y){
            mx = x;
            prim = i;
            my = y;
        }else if(my == y  &&  mx > x){
            my = y;
            prim = i;
        }
    }
    slope.resize(n);
    j = 1;
    for(int i = 0; i < n; i++){
        if(i != prim){
            if(v[j].l - mx == 0){
                slope[j].l = 0;
            }else{
                slope[j].l = (v[j].c - my) / (v[j].l - mx);
            }
            slope[j].c = j;
            j++;
        }
    }
    sort(slope.begin() + 1, slope.end(), cmp);
    st.push_back(slope[0].c);
    st.push_back(slope[1].c);
    /*for(int i = 0; i < n - 1; i++){
        cout << slope[i].l << " " << slope[i].c << "\n";
    }*/
    int p1, p2, p3, k;
    for(int i = 2; i < n; i++){
        p1 = st[st.size() - 2];
        p2 = st[st.size() - 1];
        k = st.size() - 1;
        p3 = slope[i].c;
        while(trigo(v[p1], v[p2], v[p3]) == true){
            st.resize(k);
            k--;
            p1 = st[st.size() - 2];
            p2 = st[st.size() - 1];
        }
        st.push_back(p3);
    }
    cout << st.size() << "\n";
    cout << fixed << setprecision(12) << v[(int)st[0]].l << " ";
    cout << fixed << setprecision(12) << v[(int)st[0]].c << "\n";
    for(int i = st.size() - 1; i > 0; i--){
        cout << fixed << setprecision(12) << v[(int)st[i]].l << " ";
        cout << fixed << setprecision(12) << v[(int)st[i]].c << "\n";
    }
    return 0;
}