Cod sursa(job #1432592)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 9 mai 2015 12:54:17
Problema Infasuratoare convexa Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 2.39 kb
#include <stdio.h>
#include <math.h>
#define EPS 0.0000000000001
#define INF 2000000000.0
#define MAXN 120000
typedef struct{
    double x, y;
}punct;
punct v[MAXN];
int n, vf, st[MAXN];
double bashtanu, barosanu;
inline int tata(int p){
    return (p-1)/2;
}
inline int fiust(int p){
    return 2*p+1;
}
inline int fiudr(int p){
    return 2*p+2;
}
inline int cmp(int a, int b){
    return (atan2(v[b].y-barosanu, v[b].x-bashtanu)>atan2(v[a].y-barosanu, v[a].x-bashtanu));
}
inline void swap(int a, int b){
    punct aux=v[a];
    v[a]=v[b];
    v[b]=aux;
}
inline void coborare(int p){
    int q, f=1;
    while((f==1)&&(fiust(p)<n)){
        q=fiust(p);
        if((fiudr(p)<n)&&(cmp(q, fiudr(p)))){
            q=fiudr(p);
        }
        if(cmp(p, q)){
            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(){
    int cn=n;
    while(n>1){
        n--;
        swap(0, n);
        coborare(0);
    }
    n=cn;
}
inline double arie(punct a, punct b, punct c){
    return a.x*b.y-a.y*b.x+b.x*c.y-b.y*c.x+c.x*a.y-c.y*a.x;
}
inline void convexHull(){
    int i;
    st[0]=n;
    st[1]=0;
    st[2]=1;
    vf=3;
    for(i=2; i<n; i++){
        while((vf>2)&&(arie(v[i], v[st[vf-1]], v[st[vf-2]])>0)){
            vf--;
        }
        st[vf++]=i;
    }
}
inline double myabs(double x){
    if(x<0){
        return -x;
    }
    return x;
}
int main(){
    int i, sefu;
    FILE *fin, *fout;
    fin=fopen("infasuratoare.in", "r");
    fout=fopen("infasuratoare.out", "w");
    fscanf(fin, "%d", &n);
    sefu=0;
    for(i=0; i<n; i++){
        fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
        if(((myabs(v[i].y-v[sefu].y)<EPS)&&(v[sefu].x>v[sefu].y))||(v[sefu].y>v[i].y)){
            sefu=i;
        }
    }
    swap(n-1, sefu);
    n--;
    bashtanu=v[n].x;
    barosanu=v[n].y;
    heapify();
    heapSort();
    for(i=1; i<n; i++){
        if(cmp(i, i-1)){
            printf("%lf %lf %lf %lf %lf %lf", bashtanu, barosanu, v[i-1].x, v[i-1].y, v[i].x, v[i].y);
        }
    }
    convexHull();
    fprintf(fout, "%d\n", vf);
    for(i=0; i<vf; i++){
        fprintf(fout, "%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}