Cod sursa(job #3217711)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 24 martie 2024 13:44:26
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef long double DL;

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

struct punct{
    DL x, y;
    bool inInfasuratoare;
};

int n;
punct puncte[Nmax];

struct stiva{
    int len = 0;
    int elemente[Nmax];

    void push(int indice){
        elemente[++len] = indice;
        puncte[indice].inInfasuratoare = 1;
    }

    bool canDelete(){
        return len > 1;
    }

    void pop(){
        puncte[elemente[len]].inInfasuratoare = 0;
        elemente[len--] = 0;
    }

    int top(){
        return elemente[len];
    }

    int pre_top(){
        return elemente[len - 1];
    }
};
stiva st;

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

void citire(){
    ifstream fin("infasuratoare.in");

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

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

void calcul_infasuratoare(){
    int sgn;

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

    st.push(1);
    puncte[1].inInfasuratoare = 0;

    sgn = 1;
    for(int i = 2; i >= 1; i += sgn){
        if(i == n){
            sgn = -1;
        }

        if(!puncte[i].inInfasuratoare){
            while(st.canDelete() && det(puncte[st.pre_top()], puncte[st.top()], puncte[i]) < EPS){
                st.pop();
            }

            st.push(i);
        }
    }
    st.pop();
}

void afisare(){
    ofstream fout("infasuratoare.out");

    fout << st.len << '\n';
    fout << setprecision(6);

    for(int i = 1; i <= st.len; i++){
        fout << puncte[st.elemente[i]].x << " " << puncte[st.elemente[i]].y << '\n';
    }
}

int main(){
    citire();

    calcul_infasuratoare();

    afisare();

    return 0;
}