Cod sursa(job #1566449)

Utilizator mirceas112Pirvu Mircea mirceas112 Data 12 ianuarie 2016 08:13:00
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>

#define N 120000
#define eps 1e-7
#define FORMULA(A,B,C)((((B.x)-(A.x))*((C.y)-(A.y))) - (((C.x)-(A.x))*((B.y)-(A.y))))

typedef struct punct {

    double x,y;
}PUNCT;

double mod(double a){
    if(a>0)return a;
    return -a;
}

int compare(PUNCT a, PUNCT b){
    if(a.y<b.y) return 1;
    if(a.y==b.y && a.x<b.x) return 1;
    return 0;
}

void convex_hull(PUNCT *a,int n){

    int i,*ok,head,p;
    int *stack;
    ok=(int *)calloc(n,sizeof(int));
    stack=(int *)malloc(n * sizeof(int));

    stack[0]=0;
    stack[1]=1;
    head=1;
    ok[1]=true;

    for(i=1,p=1;i>-1;i += (p = (i==n ? -p :p))){
        if(ok[i]==true)continue;
        while(head >=1 && FORMULA(a[stack[head-1]],a[stack[head]],a[i])>0)
            ok[stack[head--]]=false;
        stack[++head]=i;
        ok[i]=true;
    }
    printf("%i\n",head );
    for(i=0;i<head;i++){

        printf("%.9lf %.9lf\n",a[stack[i]].x,a[stack[i]].y);
    }
}
int main()
{
 int i,n;
    PUNCT *v;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratare.out","w",stdout);
    scanf("%i",&n);
    v=(PUNCT *)malloc(n *sizeof(PUNCT));
    for(i=0;i<n;i++)
        scanf("%lf %lf",&v[i].x,&v[i].y);

    std::sort(v,v+n,compare);

    convex_hull(v,n);
}