Cod sursa(job #1472525)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 12:07:51
Problema Infasuratoare convexa Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
int n,p,i,t,s[120010];
typedef struct { double x,y; }P;
P v[120010],r,u[120010];
double A(P a,P b,P c) { return (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;
    M(l,m),M(m+1,r);
    for(i=k=l,j=m+1;i<=m||j<=r;)
    if(j>r||(i<=m&&A(v[1],v[i],v[j])<0))
        u[k++]=v[i++];
    else
        u[k++]=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;
    r=v[1],v[1]=v[p],v[p]=r,M(2,n),s[++t]=1;
    for(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);
}