Pagini recente » Cod sursa (job #630004) | Monitorul de evaluare | Cod sursa (job #512802) | Cod sursa (job #1674655) | Cod sursa (job #3301136)
#include <stdio.h>
#include <stdlib.h>
typedef struct { double x, y; } P;
int cmp(const void *a, const void *b){
P *p=(P*)a, *q=(P*)b;
if(p->x<q->x) return -1;
if(p->x>q->x) return 1;
if(p->y<q->y) return -1;
if(p->y>q->y) return 1;
return 0;
}
double cross(P a, P b, P c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int main(){
int n;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
if(scanf("%d",&n)!=1) return 0;
P *a = malloc(n*sizeof(P));
for(int i=0;i<n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
qsort(a,n,sizeof(P),cmp);
P *h = malloc(2*n*sizeof(P));
int m=0;
for(int i=0;i<n;i++){
while(m>=2 && cross(h[m-2],h[m-1],a[i])<=0) m--;
h[m++]=a[i];
}
int t = m;
for(int i=n-2;i>=0;i--){
while(m>t && cross(h[m-2],h[m-1],a[i])<=0) m--;
h[m++]=a[i];
}
if(m>1) m--;
int start = 0;
for(int i=1;i<m;i++){
if(h[i].y < h[start].y || (h[i].y==h[start].y && h[i].x < h[start].x))
start = i;
}
printf("%d\n",m);
for(int i=0;i<m;i++){
int idx = (start+i)%m;
printf("%.6f %.6f\n", h[idx].x, h[idx].y);
}
return 0;
}