Pagini recente » Cod sursa (job #280239) | Cod sursa (job #1413861) | Cod sursa (job #1884406) | Cod sursa (job #1931383) | Cod sursa (job #312110)
Cod sursa(job #312110)
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define N 120001
double x[N],y[N],c[N];
int idx[N],urm[N],prev[N],n;
int good(double vx,double vy,double ux,double uy)
{if(uy*vx-vy*ux>.0)return 1;
else return 0;
}
void quick(int st,int dr)
{int s=st,d=dr,aux;
double p=c[idx[st+rand()%(dr-st+1)]];
while(s<d)
{while(c[idx[s]]>p)s++;
while(c[idx[d]]<p)d--;
if(s<=d)
{aux=idx[s];idx[s]=idx[d];idx[d]=aux;
s++;
d--;
}
}
if(s<dr)quick(s,dr);
if(st<d)quick(st,d);
}
int main ()
{int i,imin,numitor,count;
double aux,minx,miny;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
{scanf("%lf %lf",&x[i],&y[i]);
}
for (i=1;i<=n;i++)idx[i]=i;
for (i=2,minx=x[1],miny=y[1],imin=1;i<=n;i++)
{if(miny>x[i])
{imin=i;minx=x[i];miny=y[i];
}
if(miny==y[i])
{if(minx>x[i])
{minx=x[i];imin=i;
}
}
}
aux=x[1];x[1]=x[imin];x[imin]=aux;
aux=y[1];y[1]=y[imin];y[imin]=aux;
for (i=2;i<=n;i++)
{c[i]=(x[i]-minx)/sqrt((x[i]-minx)*(x[i]-minx)+(y[i]-miny)*(y[i]-miny));
}
quick(2,n);
for (i=1;i<n;i++)
{urm[i]=i+1;
prev[i+1]=i;
}
urm[n]=0;
i=1;
while(urm[urm[i]])
{while(good(x[idx[urm[urm[i]]]]-x[idx[urm[i]]],y[idx[urm[urm[i]]]]-y[idx[urm[i]]],x[idx[urm[i]]]-x[idx[i]],y[idx[urm[i]]]-y[idx[i]]))
{urm[i]=urm[urm[i]];
prev[urm[i]]=i;
i=prev[i];
}
i=urm[i];
}
for (i=1,count=0;i;i=urm[i])
{count++;
}
printf("%d\n",count);
for (i=1;i;i=urm[i])
{printf("%lf %lf\n",x[idx[i]],y[idx[i]]);
}
return 0;
}