Cod sursa(job #2839050)

Utilizator Savu_Stefan_CatalinSavu Stefan Catalin Savu_Stefan_Catalin Data 25 ianuarie 2022 10:34:59
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct nya{long double xx,yy;};
nya a[500005];
long long  i,n,nr,st[500005],sel[500005],ung[5000005],j;
long double mi,un1,un2,ii,jj,jj1,jj2;
int cmp(nya a,nya b)
{
    return make_pair(a.xx,a.yy)<make_pair(b.xx,b.yy);
}
long double det(nya a,nya b,nya c)
{
    return a.xx*b.yy+b.xx*c.yy+a.yy*c.xx-b.yy*c.xx-a.yy*b.xx-a.xx*c.yy;
}
int main()
{
    cin>>n;
    for (i=1;i<=n;++i)
    {
        cin>>a[i].xx>>a[i].yy;
    }
    sort(a+1,a+n+1,cmp);
    st[1]=1;
    st[2]=2;
    nr=2;
    for (i=3;i<=n;++i)
    {
        while (nr>1&&det(a[st[nr-1]],a[st[nr]],a[i])>=0)
        {
            sel[st[nr]]=0;
            nr--;
        }
        sel[i]=1;
        st[++nr]=i;
    }
    for (i=n;i>=1;--i)
    {
        if (sel[i]==0)
        {
        while (nr>1&&det(a[st[nr-1]],a[st[nr]],a[i])>=0)
        {
            sel[st[nr]]=0;
            nr--;
        }
        sel[i]=1;
        st[++nr]=i;
        }
    }
    nr--;
    cout<<nr<<'\n';
    for (i=nr;i>=1;--i)
    cout<<a[st[i]].xx<<" "<<a[st[i]].yy<<'\n';
    return 0;
}