Cod sursa(job #3205162)

Utilizator BreabanDanielBreaban Daniel-Vasile BreabanDaniel Data 18 februarie 2024 23:51:06
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 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;
vector <pair<double,double>> v;
vector <pair<double,double>> s;
int det(double x1,double y1,double x2,double y2,double x3,double y3);
bool sortare(pair<double,double> x,pair<double,double> y)
{
    if(x.first==minx && x.second==miny)
        return 1;
    if(y.first==minx && y.second==miny)
        return 0;
    if(det(minx,miny,x.first,x.second,y.first,y.second)==-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;
        }
        v.push_back({x,y});
    }
    sort(v.begin(),v.end(),sortare);
    s.push_back({minx,miny});
    for(int i=1;i<v.size();i++)
    {
        if(s.size()==1)
            s.push_back({v[i].first,v[i].second});
        else
        {
            while(det(s[s.size()-2].first,s[s.size()-2].second,s[s.size()-1].first,s[s.size()-1].second,v[i].first,v[i].second)==1 && s.size()>=2)
                s.pop_back();
            s.push_back({v[i].first,v[i].second});

        }
    }
        while(det(s[s.size()-2].first,s[s.size()-2].second,s[s.size()-1].first,s[s.size()-1].second,s[0].first,s[0].second)==1  && s.size()>2)
            s.pop_back();
    fout<<s.size()<<'\n';
    for(int i=s.size()-1;i>=0;i--)
    {
        fout<<setprecision(5)<<fixed;
        fout<<s[i].first<<' '<<s[i].second<<'\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;
}