Cod sursa(job #3146423)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 20 august 2023 22:44:49
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n;

pair<double,double> v[120005];

pair<double,double> st[120005];

int k;

double angle(pair<double,double> a ,pair<double,double> b,pair<double,double> c)
{
  return (b.first-a.first)*(c.second-a.second) - (b.second-a.second)*(c.first-a.first);
}
bool cmp(pair<double,double> a,pair<double,double> b)
{
    return angle(v[1],a,b)<0;
}



int main()
{
    fin>>n;
    int min_ind=1;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i].first>>v[i].second;
        if(v[i].first < v[min_ind].first ||
          (v[i].first==v[min_ind].first &&  v[i].second<=v[min_ind].second) )
        min_ind=i;
    }
    swap(v[1],v[min_ind]);
    sort(v+2,v+n+1,cmp);
    k=2;
    st[1]=v[1];
    st[2]=v[2];
    for(int i=3;i<=n;i++)
    {
        while(k>=2 && angle(st[k-1],st[k],v[i])>0)
            k--;
        st[++k]=v[i];
    }
    fout<<k<<'\n';
    for(int i=k;i>=1;i--)
    {
        fout<<fixed<<setprecision(6)<<st[i].first<<' '<<st[i].second<<'\n';
    }
}