Pagini recente » Cod sursa (job #2585391) | Cod sursa (job #803164) | Cod sursa (job #2257186) | Cod sursa (job #669598) | Cod sursa (job #410288)
Cod sursa(job #410288)
#include <stdio.h>
#define Nmax 120100
struct punct{
double x,y;
};
punct p[Nmax];
int n,vf,st[Nmax];
double minx,miny;
int cmp(punct i,punct j,punct k)
{
double x=(j.x-i.x)*(k.y-i.y) - (k.x-i.x)*(j.y-i.y);
if(x>0) return 1;
if(x<0) return -1;
return 0;
}
void qsort(int st,int dr)
{
int i=st,j=dr;
punct elem=p[(i+j)/2],tmp;
do
{
while(cmp(p[1],p[i],elem)==1) ++i;
while(cmp(p[1],elem,p[j])==1) --j;
if(i<=j)
{
tmp=p[i];
p[i]=p[j];
p[j]=tmp;
++i;
--j;
}
}while(i<=j);
if(i<dr) qsort(i,dr);
if(j>st) qsort(st,j);
}
int main()
{
int i;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if(p[i].x<minx)
{
punct elem=p[i];
p[i]=p[1];
p[1]=elem;
minx=p[1].x;
miny=p[1].y;
}
else
if(p[i].x==minx && p[i].y<miny)
{
punct elem=p[i];
p[i]=p[1];
p[1]=elem;
miny=p[i].y;
}
}
qsort(2,n);
st[++vf]=1;
for(i=2;i<=n;++i)
{
while(vf>1 && cmp(p[st[vf-1]],p[st[vf]],p[i])==-1)
--vf;
st[++vf]=i;
}
printf("%d\n",vf);
for(i=1;i<=vf;++i)
printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);
return 0;
}