Cod sursa(job #3205167)

Utilizator BreabanDanielBreaban Daniel-Vasile BreabanDaniel Data 19 februarie 2024 00:28:18
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.31 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double minx=1000000,miny=1000000;
int poz;
vector <pair<double,pair<double,int>>> v;
vector <pair<double,pair<double,int>>> s;
int det(double x1,double y1,double x2,double y2,double x3,double y3);
bool sortare(pair<double,pair<double,int>> x,pair<double,pair<double,int>> y)
{
    if(x.first==minx && x.second.first==miny)
        return 1;
    if(y.first==minx && y.second.first==miny)
        return 0;
    if(det(x.first,x.second.first,minx,miny,y.first,y.second.first)==-1)
        return 1;
    return 0;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        double x,y;
        fin>>x>>y;
        if(minx>x)
        {
            minx=x;
            miny=y;
            poz=i;
        }
        v.push_back({x,{y,i}});
    }
    sort(v.begin(),v.end(),sortare);
    s.push_back({minx,{miny,poz}});
    for(int i=1;i<v.size();i++)
    {
        if(s.size()==1)
            s.push_back({v[i].first,{v[i].second.first,v[i].second.second}});
        else
        {
            while(det(s[s.size()-1].first,s[s.size()-1].second.first,s[s.size()-2].first,s[s.size()-2].second.first,v[i].first,v[i].second.first)==1 && s.size()>=2)
                s.pop_back();
            s.push_back({v[i].first,{v[i].second.first,v[i].second.second}});

        }
    }
        while(det(s[s.size()-1].first,s[s.size()-1].second.first,s[s.size()-2].first,s[s.size()-2].second.first,s[0].first,s[0].second.first)==1  && s.size()>2)
            s.pop_back();
    int minim=1000000;
    for(int i=0;i<s.size();i++)
    {
        if(minim>s[i].second.second)
        {
            minim=s[i].second.second;
            poz=i;
        }
    }
    for(int i=poz;i<s.size();i++)
    {
        fout<<setprecision(5)<<fixed;
        fout<<s[i].first<<' '<<s[i].second.first<<'\n';
    }
        for(int i=0;i<poz;i++)
    {
        fout<<setprecision(5)<<fixed;
        fout<<s[i].first<<' '<<s[i].second.first<<'\n';
    }
    return 0;
}
int det(double x1,double y1,double x2,double y2,double x3,double y3)
{
    double aux=(x1*y2+x2*y3+y1*x3)-(x3*y2+y3*x1+x2*y1);
    if(aux<0)
        return -1;
    return 1;
}