Pagini recente » Cod sursa (job #2131741) | Cod sursa (job #501423) | Cod sursa (job #3193665) | Cod sursa (job #2184216) | Cod sursa (job #266263)
Cod sursa(job #266263)
#include <stdio.h>
#define nmax 120001
struct p{double x,y;};
p A[nmax];
int st[nmax],l;
int pivot(int st,int dr)
{
int s0=0,d0=-1,aux;
while (st<dr)
{
if ((double)(A[dr].x-A[1].x)*(A[st].y-A[1].y) < (double)(A[st].x-A[1].x)*(A[dr].y-A[1].y))
{
A[0] = A[dr];
A[dr] = A[st];
A[st] = A[0];
aux = -s0;
s0 = -d0;
d0 = aux;
}
st+=s0;
dr+=d0;
}
return st;
}
int cmp(p A,p B, p C)
{
double s = (A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x);
if (s<0) return 1;
return 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,k;
scanf("%d\n",&n);
scanf("%lf %lf \n",&A[1].x,&A[1].y);
k=1;
for (i=2;i<=n;i++)
{
scanf("%lf %lf \n",&A[i].x,&A[i].y);
//printf("%lf %lf \n",A[i].x,A[i].y);
if (A[i].x<A[k].x) k=i;
else if ((A[i].x==A[k].x && A[i].y<A[i].y)) k=i;
}
A[0] = A[1];
A[1] = A[k];
A[k] = A[0];
sort(2,n);
l=1;
st[l]=1;
for (i=2;i<=n;i++)
{
while (l>=2 && cmp(A[st[l]],A[st[l-1]],A[i])) l--;
st[++l]=i;
}
printf("%d\n",l);
while (l)
{
printf("%lf %lf\n",A[st[l]].x,A[st[l]].y);
l--;
}
return 0;
}