Cod sursa(job #2869896)

Utilizator RTG123Razvan Diaconescu RTG123 Data 11 martie 2022 21:55:21
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,used[120001],nr;
pair <double,double> v[120001];
int st[120001];
bool cmp (pair<double,double> a,pair <double,double> b)
{
    if (a.second>b.second)
    {
        return 0;
    }
    else if (a.second==b.second)
    {
        if (a.first>b.first)
            return 1;
        else return 0;
    }
    else return 1;
}
double det (pair<double,double> a,pair <double,double> b,pair <double,double> c)
{
    return a.first*b.second+b.first*c.second+c.first*a.second-a.second*b.first-a.first*c.second-c.first*b.second;
}
int main()
{
    f>>n;
    for (int i=1; i<=n; i++)
    {
        f>>v[i].first>>v[i].second;
    }
    sort(v+1,v+1+n,cmp);
    //st.push_back(make_pair(v[1].first,v[1].second));
    //st.push_back(make_pair(v[2].first,v[2].second));
    int i=3;
    st[1]=1;
    st[2]=2;
    used[2]=1;
    nr=2;
    while (i<=n)
    {
        if (used[i]==0)
        {
            while (nr>=2 && det(v[st[nr-1]],v[st[nr]],v[i])<=0)
            {
                used[st[nr]]=0;
                nr--;
            }
            nr++;
            st[nr]=i;
            used[st[nr]]=1;
        }
        i++;
    }
    i--;
    while (i>=1)
    {
        if (used[i]==0)
        {
            while (nr>=2 && det(v[st[nr-1]],v[st[nr]],v[i])<=0)
            {
                used[st[nr]]=0;
                nr--;
            }
            nr++;
            st[nr]=i;
            used[st[nr]]=1;
        }
        i--;
    }
    g<<nr-1<<'\n';
  //  g<<st.size()+sf.size()-2<<'\n';
    g<<fixed<<setprecision(6);
    for (int j=1; j<nr; j++)
    {
        g<<v[st[j]].first<<' '<<v[st[j]].second<<'\n';
    }
    /*for (int j=1; j<sf.size()-1; j++)
    {
        g<<setprecision(6)<<sf[j].first<<' '<<sf[j].second<<'\n';
    }*/
    /*while (!st.empty())
    {
        cout<<st.back().first<<' '<<st.back().second<<'\n';
    }*/
   // while (!st.empty())
   // {
     //   cout<<st.top().first<<' '<<st.top().second<<'\n';
    //    st.pop();
   // }
        //cout<<v[i].first<<' '<<v[i].second<<'\n';
    return 0;
}