Cod sursa(job #3180653)

Utilizator vladutzu_finutzuVlad Cacenschi vladutzu_finutzu Data 5 decembrie 2023 18:31:45
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define LD double
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const LD E = 0.000000000001;
bool is_to_the_left(pair<LD, LD> a, pair<LD, LD> b, pair<LD, LD> c){
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first) <= E;
}
int main(){
    int n;
    cin>>n;
    vector<pair<LD, LD> > p(n);

    for(int i=0; i<n; i++)
        cin>>p[i].second>>p[i].first;

    sort(p.begin(), p.end());
    vector<int> st(1);
    vector<bool> in_stack(n);
    int sign = 1;

    for(int i=1; i >= 0; i += sign){
        if(i == n - 1)
            sign = -1;
        
        if(in_stack[i])
            continue;

        int l = st.size() - 1;

        while(st.size() > 1 and !is_to_the_left(p[st[l-1]], p[st[l]], p[i]))
            in_stack[st[l]] = false, st.pop_back(), l--;
        
        st.push_back(i);
        in_stack[i] = true;
    }
    st.pop_back();
    cout<<st.size()<<'\n';

    for(int i:st)
        cout<<p[i].second<<" "<<p[i].first<<'\n';

    return 0;
}