Cod sursa(job #1472486)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 august 2015 09:49:22
Problema Infasuratoare convexa Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#define M_PI 3.14159
double x[120000],y[120000],l,a,g;
int i,n,u[120000],v[120000],m=1,c,p,t,o;
int main() {
    freopen("infasuratoare.in","r",stdin),freopen("infasuratoare.out","w",stdout),scanf("%d",&n),x[0]=y[0]=1000000000;
    for(i=1;i<=n;++i)
        scanf("%lf%lf",&x[i],&y[i]);
    for(i=1;i<=n;++i)
    if(x[i]<x[p])
        p=i;
    c=p;
    for(;m||p!=c;) {
        m=0,v[t++]=o=c,a=10000;
        for(i=1;i<=n;++i) {
            if(u[i]||i==c)
                continue;
            g=atan2(x[i]-x[c],y[i]-y[c]);
            if(g<0)
                g+=2*M_PI;
            g-=l;
            if(g<0)
                g+=2*M_PI;
            if(a>g)
                a=g,o=i;
        }
        l=atan2(x[o]-x[c],y[o]-y[c]);
        if(l<0)
            l+=2*M_PI;
        c=o,u[c]=1;
    }
    printf("%d\n",t);
    for(i=t-1;i>=0;i--)
        printf("%lf %lf\n",x[v[i]],y[v[i]]);
}