Cod sursa(job #2980563)

Utilizator SeracovanuEdwardSeracovanu Edward SeracovanuEdward Data 16 februarie 2023 17:22:50
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#define pdd pair<double,double>

using namespace std;

int const nmax = 120005;

int n;
pdd A[nmax];
pdd minn;
stack <pdd> st;

double semn(pdd a ,pdd b , pdd c){
return a.first * b.second + b.first * c.second + c.first * a.second - a.second * b.first - b.second * c.first - c.second * a.first;
}

bool comp(pdd a , pdd b){
return semn(minn , a , b) > 0;
}

pdd next_top(){
auto a = st.top();
st.pop();
auto b = st.top();
st.push(a);
return b;
}

int main()
{
    freopen("infasuratoare.in" , "r" , stdin);
    freopen("infasuratoare.out" , "w" ,stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n;
    minn.first = 2e9;
    minn.second = 2e9;
    int minni = 0;
    for(int i = 1;i <= n; ++i){
        cin >> A[i].first >> A[i].second;
        if(A[i].second < minn.second)
            minn = A[i]  , minni = i;
        else if(A[i].second == minn.second && A[i].first < minn.first)
                    minn = A[i] , minni = i;
    }
    swap(A[1] , A[minni]);
    sort(A + 2 , A + n + 1 , comp);
    st.push(A[1]);
    st.push(A[2]);
    st.push(A[3]);
    for(int i = 4;i <= n; ++i){
        while(st.size() > 2 && semn(next_top(),st.top(),A[i]) < 0)
            st.pop();
        st.push(A[i]);
    }
    cout << st.size() << "\n";
    while(!st.empty()){
        cout << fixed << setprecision(8) << st.top().first << " " << st.top().second << "\n";
        st.pop();
    }
}