Pagini recente » iiot_5 | Cod sursa (job #1565500) | Cod sursa (job #1496128) | Cod sursa (job #1783549) | Cod sursa (job #1472493)
#include<stdio.h>
#include<stdlib.h>
typedef struct { double x,y; }P;
P v[120005];
int s[120005],h,n,i,u[120005],p;
int A(const void *a,const void *b) {
P *c=(P*)a,*d=(P*)b;
return c->x<d->x||(c->x==d->x&&c->y<d->y);
}
double C(P o,P a,P b) { return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y); }
int main() {
freopen("infasuratoare.in","r",stdin),freopen("infasuratoare.out","w",stdout),scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
qsort(v,sizeof(v)/sizeof(P),sizeof(P),A),s[1]=1,s[2]=h=2,u[2]=1;
for(i=p=1;i;i+=(p=(i==n?-p:p))) {
if(u[i])
continue;
for(;h>1&&C(v[s[h-1]],v[s[h]],v[i])<1e-12;u[s[h--]]=0);
s[++h]=i,u[i]=1;
}
printf("%d\n",h-1);
for(i=1;i<h;i++)
printf("%.6lf %.6lf\n",v[s[i]].x,v[s[i]].y);
}