Cod sursa(job #1472523)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 12:02:11
Problema Infasuratoare convexa Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.76 kb
#include<stdio.h>
int n,p,i,t,s[120010];
typedef struct { double x,y; }P;
P v[120010],r;
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); }
int C(const void *a,const void *b) {
    P *c=(P*)a,*d=(P*)b;
    return A(v[1],*c,*d)<0;
}
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,qsort(&v[2],sizeof(v)/sizeof(P),sizeof(P),C),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);
}