Cod sursa(job #2926691)

Utilizator Gica-gicutaGeorge Gica-gicuta Data 18 octombrie 2022 13:52:52
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
long double r=0;
vector <pair<long double,long double>>v,st,st1,rez;
long double aria(pair<long double,long double>a1,pair<long double,long double>a2,pair<long double,long double>a3)
{
    return a1.first*a2.second+a2.first*a3.second+a3.first*a1.second-a1.second*a2.first-a2.second*a3.first-a3.second*a1.first;
}
long double vir(pair<long double,long double> a1,pair<long double,long double> a2,pair<long double,long double> a3)
{
    long double ar=aria(a1,a2,a3);
    if(ar<0)
        return -1;
    if(ar>0)
        return 1;
    return 0;
}
bool comp(pair<long double,long double>x,pair<long double,long double>y)
{
    long double ar=aria(v[0],x,y);
    if(ar>0)
        return true;
    return false;
}
int main()
{
    pair<long double,long double>pt;
    long double n;
    fin>>n;
    for(long double i=1; i<=n; i++)
    {
        fin>>pt.first>>pt.second;
        v.push_back(pt);
    }
    for(long double i=1; i<n; i++)
    {
        if(v[r]>v[i])
            r=i;
    }
    swap(v[0],v[r]);
    sort(v.begin()+1,v.end(),comp);
    st.push_back(v[0]);
    st.push_back(v[1]);
    for(auto it:v)
    {
        long double nr=st.size();
        pair<long double,long double> a1,a2,a3;
        a2=st[nr-1];
        a1=st[nr-2];
        a3=it;
        while(vir(a1,a2,a3)!=1&&st.size()>1)
        {
//                    fout<<a1.first<<" "<<a2.first<<'\n';
            auto it1=st.end();
            it1--;
            st.erase(it1,st.end());
            nr=st.size();
            a2=st[nr-1];
            a1=st[nr-2];
        }
//                fout<<st.back().first<<" "<<st.back().second<<" "<<it.first<<" "<<it.second<<'\n';
        st.push_back(it);
    }
    fout<<st.size()<<'\n';
    for(auto it:st)
    {
        fout<<fixed<<setprecision(12)<<it.first;
        fout<<" ";
        fout<<fixed<<setprecision(12)<<it.second;
        fout<<'\n';
    }
    return 0;
}