Cod sursa(job #1552492)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 18 decembrie 2015 10:49:33
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <cstdio>
#define MAXN 100000
double x[MAXN],y[MAXN];
int stiv[MAXN],punct[MAXN];
inline void swap(int b,int e,double *v){
    double aux=v[b];
    v[b]=v[e];
    v[e]=aux;
}
void myqsort(int begin,int end,double *v){
    int b=begin,e=end;
    double pivot=v[(b+e)/2];
    while(b<=e){
        while(v[b]<pivot) b++;
        while(v[e]>pivot) e--;
        if(b<=e){
            swap(b,e,x);
            swap(b,e,y);
            b++;e--;
        }
    }
    if(begin<e) myqsort(begin,e,v);
    if(b<end) myqsort(b,end,v);
}
inline double aria(double x1,double y1,double x2,double y2,double x3,double 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,j;
    fi=fopen("infasuratoare.in" ,"r");
    fout=fopen("infasuratoare.out" ,"w");
    fscanf(fi,"%d" ,&n);
    for(i=0;i<n;i++)
       fscanf(fi,"%lf%lf" ,&x[i],&y[i]);
    myqsort(0,n-1,y);
    i=0;
    while(i<n){
        j=i;
        while(j+1<n&&y[j]==y[j+1])
            j++;
        myqsort(i,j,x);
        i=j+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,"%f %f\n" ,x[punct[i]],y[punct[i]]);
    fclose(fi);
    fclose(fout);
    return 0;
}