Cod sursa(job #2926428)

Utilizator Gica-gicutaGeorge Gica-gicuta Data 17 octombrie 2022 19:27:35
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.87 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
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 cmp(pair<int,int>x,pair<int,int>y)
{
    return x.first*y.second>x.second*y.first;
}
vector <pair<long double,long double>>v,st,st1,rez;
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);
    }
    sort(v.begin(),v.end());
    for(auto it:v)
    {
            if(st.size()<2)
                st.push_back(it);
            else
            {
                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);
            }
    }
    for(int i=v.size()-1; i>=0; i--)
    {
            pair<int,int>it=v[i];
            if(st1.size()<2)
                st1.push_back(it);
            else
            {
                long double nr=st1.size();
                pair<long double,long double> a1,a2,a3;
                a2=st1[nr-1];
                a1=st1[nr-2];
                a3=it;
                while(vir(a1,a2,a3)==-1&&st1.size()>1)
                {
                    auto it1=st1.end();
                    it1--;
                    st1.erase(it1,st1.end());
                    nr=st1.size();
                    a2=st1[nr-1];
                    a1=st1[nr-2];
                }
                st1.push_back(it);
            }
    }
    for(auto it:st)
        rez.push_back(it);
    for(int i=1; i<st1.size()-1; i++)
        rez.push_back(st1[i]);
    sort(rez.begin(),rez.end(),cmp);
    fout<<rez.size()<<'\n';
    for(auto it:rez)
    {
        fout<<fixed<<setprecision(12)<<it.first;
        fout<<" ";
        fout<<fixed<<setprecision(12)<<it.second;
        fout<<'\n';
    }
    return 0;
}