Cod sursa(job #2878506)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 26 martie 2022 23:35:04
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
int st[120001],h[20],rez[120001];
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct ura
{
    long double x,y;
    int o;
}p[120001],p1[120001],p2[120001];
void schimb(ura &a, ura b)
{
    a.x=b.x;
    a.y=b.y;
    a.o=b.o;
}
int arie(ura a, ura b, ura c)
{
    return (a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x);
}
bool cmp( ura a, ura b)
{
    if(a.y<b.y)
        return true;
    if(a.y>b.y)
        return false;
    if(a.x<b.x)
        return true;
    return false;
}
int main()
{
    int n,i,k1=1,k2=1,k,ok;
    long double a;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>p[i].x>>p[i].y;
    sort(p+1,p+n+1,cmp);
    p[1].o=1;
    p[n].o=n;
    schimb(p2[1],p[1]);
    schimb(p1[1],p[1]);
    for(i=2;i<n;i++)
    {
        a=arie(p[1],p[n],p[i]);
        p[i].o=i;
        if(a<0)///punctul se afla la dreapta
        {
            k2++;
            schimb(p2[k2],p[i]);
        }
        else
        {
            k1++;
            schimb(p1[k1],p[i]);
        }
    }
    k2++;
    k1++;
    schimb(p2[k2],p[n]);
    schimb(p1[k1],p[n]);
    st[1]=1;
    st[2]=2;
    k=2;
    for(i=3;i<=k2;i++)
    {
        ok=0;
        while(k>=2&&ok==0)
        {
            a=arie(p2[st[k-1]],p2[st[k]],p2[i]);
            if(a>0)
                ok=1;
            else
                k--;
        }
        k++;
        st[k]=i;
    }
    for(i=1;i<=k;i++)
        rez[i]=p2[st[i]].o;
    int f=k;
    st[1]=1;
    st[2]=2;
    k=2;
    for(i=3;i<=k1;i++)
    {
        ok=0;
        while(k>=2&&ok==0)
        {
            a=arie(p1[st[k-1]]  ,p1[st[k]],p1[i]);
            if(a<0)
                ok=1;
            else
                k--;
        }
        k++;
        st[k]=i;
    }
    for(i=2;i<k;i++)
        rez[k+f-i]=p1[st[i]].o;
    f+=k-2;
    cout<<f<<'\n';
    for(i=1;i<=f;i++)
        cout<<fixed<<setprecision(6)<<p[rez[i]].x<<" "<<p[rez[i]].y<<'\n';
    return 0;
}