Cod sursa(job #1472502)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 11:24:59
Problema Infasuratoare convexa Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct { double x,y; }P;
P v[120005],r,w[120005];
int s[120005],h,n,i,p;
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&&(v[i].x<v[j].x||(v[i].x==v[j].y&&v[i].y<v[j].y))))
        w[k++]=v[i++];
    else
        w[k++]=v[j++];
    for(k=l;k<=r;k++)
        v[i]=w[i];
}
double C(P o,P a,P b) { return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y); }
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);
        if(v[i].x<v[p].x||(v[i].x==v[p].x&&v[i].y<v[p].y))
            p=i;
    }
    r=v[1],v[1]=v[p],v[p]=r,s[++h]=1,M(2,n);
    for(i=2;i<=n;i++) {
        for(;h>1&&C(v[s[h-1]],v[s[h]],v[i])>0;h--);
        s[++h]=i;
    }
    printf("%d\n",h);
    for(i=h;i;i--)
        printf("%.6lf %.6lf\n",v[s[i]].x,v[s[i]].y);
}