Cod sursa(job #3159118)

Utilizator VespaOlaru Amelia Vespa Data 20 octombrie 2023 18:56:49
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <algorithm>
#include <vector>
#include <stack>
#include <iomanip>
#include <fstream>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct point
{
    double x,y;
};
enum orientare
{
    TRIGONOMETRIC,
    ORAR,
    COLIN,
};

orientare calcOrientare(point a,point b,point c)
{
    double det=(a.y-b.y)*(c.x-b.x)-(a.x-b.x)*(c.y-b.y);
    if(det>0)
        return TRIGONOMETRIC;
    if(det<0)
        return ORAR;
    if(det==0)
        return COLIN;
}


vector<point>V;

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

//vector<point>sol;//vectorul de solutii
vector<point>S;//o "stiva"
vector<point>S2;
void fun()
{
    ///iau pe primul punct
    S.push_back(V[0]);///bag primul punct in stiva
    S.push_back(V[1]);///al doilea
    //S.push_back(V[3]);
point aux=V[0];//de unde plec gen

    for(int i=2;i<V.size();i++)
    {
        point p3=V[i];
        point p2=S[S.size()-1];
        point p1=S[S.size()-2];
        while(calcOrientare(S[S.size()-2],S[S.size()-1],p3)==TRIGONOMETRIC)
            S.pop_back();
        S.push_back(p3);

    }
    ///a doua jum din poligon
    S2.push_back(V[V.size()-1-1]);
    S2.push_back(V[V.size()-1-2]);

    for(int i=V.size()-1-3;i>=0;i--)
    {
        point p3=V[i];
        point p2=S2[S2.size()-1];
        point p1=S2[S2.size()-2];
        while(calcOrientare(S2[S2.size()-2],S2[S2.size()-1],p3)==TRIGONOMETRIC)
            S2.pop_back();
        S2.push_back(p3);
    }


}

int main()
{
    int n;
    fin>>n;
    for(int i=0; i<n; i++)
    {
        double x,y;
        fin>>x>>y;
        V.push_back({x,y});
    }
    sort(V.begin(),V.end(),cmp);
    //for(auto&i:V)
        //cout<<i.x<<" "<<i.y<<'\n';
    fun();
    for(auto&i:S)
        fout<<fixed<<setprecision(6)<<i.x<<" "<<i.y<<'\n';
    //cout<<"a doua jum"<<'\n';

    for(int i=0;i<=S2.size()-2;i++)
        fout<<fixed<<setprecision(6)<<S2[i].x<<" "<<S2[i].y<<'\n';
    return 0;
}