Pagini recente » Cod sursa (job #1672628) | Cod sursa (job #902482) | Cod sursa (job #2399184) | Cod sursa (job #2900432) | Cod sursa (job #265831)
Cod sursa(job #265831)
#include <stdio.h>
double x[120001],y[120001];
int k,s[120001],l;
int pivot(int i,int j)
{
int si=0,sj=-1,aux;
double ax;
while (i<j)
{
if ((long double)(x[j]-x[1])*(y[i]-y[1]) < (long double)(x[i]-x[1])*(y[j]-y[1]));
{
ax = x[i];x[i]=x[j];x[j]=ax;
ax = y[i];y[i]=y[j];y[j]=ax;
aux = -sj;
sj = -si;
si = aux;
}
i+=si;
j+=sj;
}
return i;
}
int semn(int x1,int x2,int x3,int y1,int y2,int y3)
{
return (long double)(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))>0;
}
void sort(int st,int dr)
{
if (st<dr)
{
int m = pivot(st,dr);
sort(st,m-1);
sort(m+1,dr);
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i;
scanf("%d\n",&n);
k=1;
scanf("%lf %lf\n",&x[1],&y[1]);
for (i=2;i<=n;i++)
{
scanf("%lf %lf\n",&x[i],&y[i]);
if (x[i]<x[k]) k=i;
else if (x[i]==x[k] && y[i]<y[k]) k=i;
}
x[0]=x[k];x[k]=x[1];x[1]=x[0];
y[0]=y[k];y[k]=y[1];y[1]=y[0];
sort(2,n);
l=2;
s[1] = 1;
s[2] = 2;
for (i=3;i<=n;i++)
{
while ((l>=2) && (!semn(x[s[l]],x[s[l-1]],x[i],y[s[l]],y[s[l-1]],y[i]))) l--;
s[++l] = i;
}
printf("%d\n",l);
while (l)
{
printf("%lf %lf\n",x[s[l]],y[s[l]]);
l--;
}
return 0;
}