Cod sursă (job #174109)

#include <cstdio>
#define MAXN 100000
float x[MAXN],y[MAXN];
int stiv[MAXN],punct[MAXN];
inline void swap(int b,int e,float *v){
    float aux=v[b];
    v[b]=v[e];
    v[e]=aux;
}
void myqsort(int begin,int end){
    int b=begin,e=end;
    float pivot=y[(b+e)/2];
    while(b<=e){
        while(y[b]<pivot) b++;
        while(y[e]>pivot) e--;
        if(b<=e){
            swap(b,e,x);
            swap(b,e,y);
            b++;e--;
        }
    }
    if(begin<e) myqsort(begin,e);
    if(b<end) myqsort(b,end);
}
inline float aria(float x1,float y1,float x2,float y2,float x3,float y3){
    return (x1*y2+x2*y3+x3*y1-y2*x3-y3*x1-y1*x2)/2;
}
int main(){
    FILE*fi,*fout;
    int i,n,ist,m;
    fi=fopen("infasuratoare.in" ,"r");
    fout=fopen("infasuratoare.out" ,"w");
    fscanf(fi,"%d" ,&n);
    for(i=0;i<n;i++)
       fscanf(fi,"%f%f" ,&x[i],&y[i]);
    myqsort(0,n-1);
    stiv[0]=0;
    stiv[1]=1;
    ist=1;
    for(i=2;i<n;i++){
        while(ist>=1&&aria(x[stiv[ist]],y[stiv[ist]],x[stiv[ist-1]],y[stiv[ist-1]],x[i],y[i])>=0)
            ist--;
        stiv[++ist]=i;
    }
    m=0;
    while(m<=ist){
        punct[m]=stiv[m];
        m++;
    }
    ist=1;
    stiv[0]=n-1;
    stiv[1]=n-2;
    for(i=n-3;i>=0;i--){
         while(ist>=1&&aria(x[stiv[ist]],y[stiv[ist]],x[stiv[ist-1]],y[stiv[ist-1]],x[i],y[i])>=0)
            ist--;
        stiv[++ist]=i;
    }
    for(i=1;i<ist;i++)
        punct[m+i-1]=stiv[i];
    m=m+ist-1;
    fprintf(fout,"%d\n" ,m);
    for(i=0;i<m;i++)
        fprintf(fout,"%.0f %.0f\n" ,x[punct[i]],y[punct[i]]);
    fclose(fi);
    fclose(fout);
    return 0;
}