Cod sursa(job #3144769)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 10 august 2023 16:09:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
pair <double,double> v[120001];
int st[120001],afis[120001];
double triunghi(int p1,int p2,int p3)
{
 return (v[p1].first-v[p2].first)*(v[p1].second-v[p3].second)-(v[p1].second-v[p2].second)*(v[p1].first-v[p3].first);
}
int main()
{
    int n,i,cnt=0,vf=0;
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i].first>>v[i].second;
    sort(v+1,v+n+1);
    vf=0;
    st[++vf]=1;
    st[++vf]=2;
    for(i=3;i<=n;i++)
    {
     while(vf>1&&triunghi(st[vf-1],st[vf],i)<-1e-12)
            vf--;
     st[++vf]=i;
    }
    cnt=vf;
    for(i=1;i<=vf;i++)
        afis[i]=st[i];
    vf=0;
    st[++vf]=n;
    st[++vf]=n-1;
    for(i=n-2;i>=1;i--)
    {
     while(vf>1&&triunghi(st[vf-1],st[vf],i)<-1e-12)
            vf--;
     st[++vf]=i;
    }
    for(i=2;i<=vf-1;i++)
        afis[++cnt]=st[i];
    out<<cnt<<'\n';
    out<<setprecision(6)<<fixed;
    for(i=1;i<=cnt;i++)
        out<<v[afis[i]].first<<" "<<v[afis[i]].second<<'\n';
    return 0;
}