Pagini recente » Profil StarGold2 | Cod sursa (job #2121764) | Cod sursa (job #1779710) | Cod sursa (job #1700119) | Cod sursa (job #265816)
Cod sursa(job #265816)
#include <stdio.h>
#define Nmax 120200
#define inf 10000000
struct p{ double x,y; };
p a[Nmax];
int n,st[Nmax],vf=1;
double minx=inf,miny=inf;
int cmp(p A,p B,p C)
{
double semn=((A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x));
if(semn>0) return 1;
if(semn<0) return -1;
return 0;
}
void qsort(int st,int dr)
{
int i=st,j=dr;
p elem=a[(i+j)/2],aux;
do
{
while(cmp(a[1],a[i],elem) == 1) ++i;
while(cmp(a[1],elem,a[j]) == 1) --j;
if(i<=j)
{
aux=a[i];
a[i]=a[j];
a[j]=aux;
++i;
--j;
}
}while(i<=j);
if(st<j) qsort(st,j);
if(i<dr) qsort(i,dr);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
if(a[i].y<miny)
{
miny=a[i].y;
minx=a[i].x;
a[0]=a[i];
a[i]=a[1];
a[1]=a[0];
}
else
if(a[i].y==miny)
if(a[i].x<minx)
{
minx=a[i].x;
a[0]=a[i];
a[i]=a[1];
a[1]=a[0];
}
}
/* for(i=1;i<=n;++i)
printf("%lf %lf\n",a[i].x,a[i].y); */
qsort(2,n);
st[vf]=1;
for(i=2;i<=n;++i)
{
while(vf>1 && cmp(a[st[vf-1]],a[st[vf]],a[i]) == -1)
--vf;
st[++vf]=i;
}
/* while(vf>1 && cmp(a[st[vf]],a[st[vf]],a[1]) == -1)
--vf; */
printf("%d\n",vf);
for(i=1;i<=vf;++i)
{
printf("%.6f %.6f\n",a[st[i]].x,a[st[i]].y);
}
return 0;
}