Cod sursa(job #2372673)

Utilizator mariastStoichitescu Maria mariast Data 7 martie 2019 10:29:47
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int st[120010],n,m,k,viz[120010];
struct punct{
    long double x,y;
}a[120010];
bool cmp(punct A,punct B){
    return A.x<B.x||(A.x==B.x&&A.y<B.y);
}
bool valid(int i,int j,int k){
    return(a[i].x*a[j].y+a[i].y*a[k].x+a[j].x*a[k].y-a[j].y*a[k].x-a[k].y*a[i].x-a[i].y*a[j].x)<0;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;++i){
        f>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);

    st[1]=1;
    st[2]=2;
    viz[2]=1;
    k=2;
    for(int i=3;i<=n;++i){
        while(k>=2&&!valid(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&&!valid(st[k-1],st[k],i))viz[st[k--]]=0;;
        st[++k]=i;
        viz[i]=1;
    }
    g<<k-1<<'\n';
    for(int i=k-1;i>=1;--i){
        g<<fixed<<setprecision(6)<<a[st[i]].x<<" "<<a[st[i]].y<<'\n';
    }

}