Cod sursa(job #2695737)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 14 ianuarie 2021 13:37:05
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include<cstdio>
const int N=120001;
int n,p,i,t,s[N];
typedef struct P
{
	double x,y;
};
P v[N],r,u[N];
#define A(a,b,c) ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y))
void M(int l,int r)
{
    if(l==r)
        return;
    int i,j,k,m=(l+r)/2;
    for(M(l,m),M(m+1,r),i=k=l,j=m+1;i<=m||j<=r;)
    	u[k++]=(j>r||(i<=m&&A(v[1],v[i],v[j])<0))?v[i++]:v[j++];
    for(i=l;i<=r;i++)
        v[i]=u[i];
}
int main()
{
    freopen("infasuratoare.in","r",stdin),freopen("infasuratoare.out","w",stdout),scanf("%d",&n);
    for(p=i=1;i<=n;i++)
        scanf("%lf%lf",&v[i].x,&v[i].y),p=v[i].x<v[p].x||(v[i].x==v[p].x&&v[i].y<v[p].y)?i:p;
    for(r=v[1],v[1]=v[p],v[p]=r,M(2,n),s[++t]=1,i=2;i<=n;i++)
	{
        for(;t>1&&A(v[s[t-1]],v[s[t]],v[i])>0;t--);
        s[++t]=i;
    }
    printf("%d\n",t);
    for(;t;t--)
        printf("%.6lf %.6lf\n",v[s[t]].x,v[s[t]].y);
}