Pagini recente » Cod sursa (job #271535) | Cod sursa (job #2354855) | Cod sursa (job #357575) | Cod sursa (job #2620299) | Cod sursa (job #350547)
Cod sursa(job #350547)
#include<fstream>
using namespace std;
int n;
struct punct
{double x,y;
} varf[120004],P[120004];
int uz[120004],st[1200004],k;
int comp(double v1, double v2)
{if(v1<v2) return +1;
if(v1>v2) return -1;
return 0;
}
int comp_varf(punct v1,punct v2)
{int r=comp(v1.x,v2.x);
if(r) return r==-1;
return comp(v1.y,v2.y)==-1;
}
int partition(int p,int r)
{punct x=varf[r];
int i=p-1;
for(int j=p;j<r;j++) {if(comp_varf(varf[j],x)==0) {i++;punct aux=varf[i];varf[i]=varf[j];varf[j]=aux;}}
punct aux2=varf[i+1];varf[i+1]=varf[r];varf[r]=aux2;
return i+1;
}
int unghi(punct a,punct b,punct c)
{return ((a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x)>0);
}
void quicksort(int p,int r)
{if(p<r)
{int q=partition(p,r);
quicksort(p,q-1);
quicksort(q+1,r);
}
}
void ConvexHull()
{quicksort(1,n);
int pas=+1;
uz[1]=0;uz[2]=1;st[1]=1;st[2]=2;k=2;int i=3;
while(!uz[1])
{
while(uz[i])
{if(i==n) pas=-1;
i+=pas;
}
while(k>=2 && unghi(varf[st[k-1]],varf[st[k]],varf[i])==0 )
uz[st[k--]]=0;
st[++k]=i;uz[i]=1;
}
for(int i=1;i<=k-1;i++)
P[i]=varf[st[i]];
P[k]=P[1];
}
int main()
{freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf %lf",&varf[i].x,&varf[i].y);
ConvexHull();
printf("%d \n",k-1);
for(int i=2;i<=k;i++)
printf("%.6lf %.6lf \n",P[i].x,P[i].y);
return 0;}