Cod sursa(job #2156290)

Utilizator mihai2003LLL LLL mihai2003 Data 8 martie 2018 17:04:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <fstream>
#include <iomanip>
using namespace std;
struct poz{
    double x,y;
    bool operator<(poz aux){
        if(aux.x==x)
            return aux.y<y;
        return aux.x<x;
    }
};
class stiva:public stack<poz>{
    public :
        poz top_l(){
            poz aux,aux2;
            aux=top();
            pop();
            aux2=top();
            push(aux);
            return aux2;
        }
};
stiva st;
bool semnarie(poz p1,poz p2,poz p3){
    return (p2.x*p1.y+p3.x*p2.y+p1.x*p3.y-p1.x*p2.y-p2.x*p3.y-p3.x*p1.y)>0;
}
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
vector<poz>v;
vector<poz>v2;
void infasuratoare1( ){
    for(int i=0;i <v.size();i++){
        while(st.size()>1 && semnarie(st.top(),st.top_l(),v[i]))
            st.pop();
        st.push(v[i]);
    }
    while(st.size()>1)
        v2.push_back(st.top()),st.pop();
    st.pop();
    for(int i=v.size()-1;i>=0;i--){
        while(st.size()>1&& semnarie(st.top(),st.top_l(),v[i]))
            st.pop();
        st.push(v[i]);
    }
     while(st.size()>1)
        v2.push_back(st.top()),st.pop();
    st.pop();
}
int main()
{
    int n;
    double aux1,aux2;
    in>>n;
    for(int i=1;i<=n;i++){
        in>>aux1>>aux2;
        v.push_back((poz){aux1,aux2});
    }
    sort(v.begin(),v.end());
    infasuratoare1();
    out<<v2.size()<<"\n";
    for(int i=0;i<v2.size();i++)
        out<<fixed<<setprecision(12)<<v2[i].x<<" "<<v2[i].y<<"\n";
    return 0;
}