Cod sursa(job #1268286)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 20 noiembrie 2014 19:51:38
Problema Infasuratoare convexa Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 2.44 kb
#include <stdio.h>
#define EPS 1e-12
#define MAXN 120000
#define INF 1000000000000000.0
int n, stiva[MAXN+1], ok[MAXN+1];
double x[MAXN], y[MAXN];
FILE *fout;
inline int tata(int a){
    return (a-1)/2;
}
inline int fiust(int a){
    return a*2+1;
}
inline int fiudr(int a){
    return a*2+2;
}
inline void swap(int a, int b){
    double aux=x[a];
    x[a]=x[b];
    x[b]=aux;
    aux=y[a];
    y[a]=y[b];
    y[b]=aux;
}
inline int trbSchimb(int a, int b){
    if(x[a]>x[b]){
        return 1;
    }
    if((x[a]==x[b])&&(y[a]>=y[b])){
        return 1;
    }
    return 0;
}
inline void coborare(int p){
    int q, f;
    f=1;
    while((f==1)&&(fiust(p)<n)){
        q=fiust(p);
        if((fiudr(p)<n)&&(trbSchimb(fiudr(p), q)==1)){
            q=fiudr(p);
        }
        if(trbSchimb(q, p)==1){
            swap(p, q);
            p=q;
        }else{
            f=0;
        }
    }
}
inline void heapify(){
    int i;
    for(i=tata(n-1); i>=0; i--){
        coborare(i);
    }
}
inline void heapSort(){
    while(n>1){
        n--;
        swap(0, n);
        coborare(0);
    }
}
inline double modul(double a){
    if(a>0){
        return a;
    }
    return -a;
}
inline double crossProduct(int a, int b, int c){
    return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a]);
}
inline void convexHull(){
    int vf, i;
    stiva[0]=0;
    stiva[1]=1;
    ok[1]=1;
    vf=2;
    for(i=1; i<n; i++){
        if(ok[i]==0){
            while((vf>=2)&&(crossProduct(stiva[vf-2], stiva[vf-1], i)<EPS)){
                vf--;
                ok[stiva[vf]]=0;
            }
            stiva[vf++]=i;
            ok[i]=1;
        }
    }
    for(i=n-1; i>0; i--){
        if(ok[i]==0){
            while((vf>=2)&&(crossProduct(stiva[vf-2], stiva[vf-1], i)<EPS)){
                vf--;
                ok[stiva[vf]]=0;
            }
            stiva[vf++]=i;
            ok[i]=1;
        }
    }
    fprintf(fout, "%d\n", vf);
    for(i=0; i<vf; i++){
        fprintf(fout, "%.6lf %.6lf\n", x[stiva[i]], y[stiva[i]]);
    }
}
int main(){
    int i, cn;
    FILE *fin;
    fin=fopen("infasuratoare.in", "r");
    fout=fopen("infasuratoare.out", "w");
    fscanf(fin, "%d", &n);
    for(i=0; i<n; i++){
        fscanf(fin, "%lf%lf", &x[i], &y[i]);
    }
    heapify();
    cn=n;
    heapSort();
    n=cn;
    convexHull();
    fclose(fin);
    fclose(fout);
    return 0;
}