Cod sursa(job #3195683)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 21 ianuarie 2024 15:04:39
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

#define DL long double

using namespace std;

const int Nmax = 120005;
const DL eps = 1e-12;

struct punct{
    DL x;
    DL y;
};

struct stiva{
    int index = 0;
    int pozitii[Nmax];
    bool inStiva[Nmax];

    void push(int x){
        inStiva[x] = 1;
        pozitii[++index] = x;
    }

    int top(){
        return pozitii[index];
    }
    int pre_top(){
        return pozitii[index - 1];
    }

    int len(){
        return index;
    }

    void pop(){
        inStiva[top()] = 0;
        pozitii[index--] = 0;
    }
};

stiva st;
punct v[Nmax];

bool cmp(punct a, punct b){
    if(a.y == b.y){
        return a.x < b.x;
    }
    return a.y < b.y;
}

DL angle(punct a, punct b, punct c){
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int main(){
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");

    int n, sgn;

    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> v[i].x >> v[i].y;
    }

    sort(v + 1, v + n + 1, cmp);

    st.index = 0;
    sgn = 1;

    st.push(1);
    st.inStiva[1] = 0;

    st.push(2);

    for(int i = 3; i >= 1; i += sgn){
        if(!st.inStiva[i]){
            while(st.len() > 1 && angle(v[st.pre_top()], v[st.top()], v[i]) <= eps){
                st.pop();
            }

            st.push(i);
        }

        if(i == n){
            sgn = -1;
        }
    }
    st.pop();

    fout << st.len() << '\n';
    fout << setprecision(6) << fixed;
    for(int i = 1; i <= st.len(); i++){
        fout << v[st.pozitii[i]].x << " " << v[st.pozitii[i]].y << '\n';
    }

    return 0;
}