Cod sursa(job #2373757)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 7 martie 2019 15:10:10
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include<bits/stdc++.h>

using namespace std;

int st[120010],n,m,k,viz[120010];

struct punct
{
    long double x,y;
} v[120010];

bool acomp(punct a,punct b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}

bool ok(int i,int j,int k)
{
    return(v[i].x*v[j].y+v[i].y*v[k].x+v[j].x*v[k].y-v[j].y*v[k].x-v[k].y*v[i].x-v[i].y*v[j].x)<0;
}

int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fin>>n;
    for(int i=1; i<=n; ++i)
    {
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,acomp);
    st[1]=1;
    st[2]=2;
    viz[2]=1;
    k=2;
    for(int i=3; i<=n; ++i)
    {
        while(k>=2&&!ok(st[k-1],st[k],i))viz[st[k--]]=0;;
        st[++k]=i;
        viz[i]=1;
    }
    for(int i=n; i>=1; --i)
    {
        if(viz[i])
        {
            continue;
        }
        while(k>=2&&!ok(st[k-1],st[k],i))
        {
            viz[st[k--]]=0;
        }
        st[++k]=i;
        viz[i]=1;
    }
    fout<<k-1<<"\n";
    for(int i=k-1; i>=1; --i)
    {
        fout<<fixed<<setprecision(12)<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
    }

}