Pagini recente » Cod sursa (job #1683837) | Cod sursa (job #1257970) | Istoria paginii runda/runda_1_biscuiti_cu_lacuste | Cod sursa (job #1811237) | Cod sursa (job #1566449)
#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);
}