Cod sursa(job #1432238)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 9 mai 2015 11:57:03
Problema Infasuratoare convexa Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 1.98 kb
#include <stdio.h>
#include <math.h>
#define INF 2000000000.0
#define MAXN 120000
typedef struct{
    double x, y;
}punct;
punct v[MAXN];
int n, vf, sefu, barosanu, st[MAXN];
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-sefu)>atan2(v[a].y-barosanu, v[a].x-sefu));
}
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 int arie(punct a, punct b, punct c){
    return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
inline void convexHull(){
    int i;
    st[0]=0;
    st[1]=1;
    st[2]=2;
    vf=3;
    for(i=3; i<n; i++){
        while((vf>2)&&(arie(v[i], v[st[vf-1]], v[st[vf-2]])>0)){
            vf--;
        }
        st[vf++]=i;
    }
}
int main(){
    int i;
    FILE *fin, *fout;
    fin=fopen("infasuratoare.in", "r");
    fout=fopen("infasuratoare.out", "w");
    fscanf(fin, "%d", &n);
    sefu=barosanu=INF;
    for(i=0; i<n; i++){
        fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
        if(barosanu>v[i].y){
            sefu=v[i].x;
            barosanu=v[i].y;
        }
    }
    heapify();
    heapSort();
    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;
}