Cod sursa(job #2839122)

Utilizator Savu_Stefan_CatalinSavu Stefan Catalin Savu_Stefan_Catalin Data 25 ianuarie 2022 12:37:02
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct nya{long double xx,yy;};
nya a[400005];
long long  i,n,nr,st[400005],sel[400005],ung[4000005],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);
}
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()
{
    in>>n;
    for (i=1;i<=n;++i)
    {
        in>>a[i].xx>>a[i].yy;
    }
    sort(a+1,a+n+1,cmp);
    st[1]=1;
    st[2]=2;
    nr=2;
    sel[2]=1;
    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;
        }
    }
    out<<nr-1<<'\n';
    for (i=nr-1;i>=1;--i)
        out<<a[st[i]].xx<<" "<<a[st[i]].yy<<'\n';
    return 0;
}