Pagini recente » Cod sursa (job #3156549) | Cod sursa (job #1826342) | Cod sursa (job #28828) | Cod sursa (job #1837031) | Cod sursa (job #288675)
Cod sursa(job #288675)
#include <stdio.h>
#include <algorithm>
using namespace std;
struct pcte{double x;double y;};
pcte p[120005],P,aux;
pcte stack[120005];
int i,j,k,l,m,n,c,q=3;
int isLeft(pcte p1,pcte p2,pcte p)
{
return ((double)(p1.x*p.y+p.x*p2.y+p2.x*p1.y)>
(double)(p2.x*p.y+p2.y*p1.x+p.x*p1.y));
}
int comp(const pcte &x,const pcte &y)
{
return isLeft(y,x,P);
}
int main()
{
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);
P.x=1000000001;P.y=1000000001;
for (i=1;i<=n;++i)
if (p[i].x<P.x||(p[i].x==P.x&&p[i].y<P.y))
P.x=p[i].x,P.y=p[i].y,c=i;
aux=p[c];p[c]=p[n];p[n]=aux;
sort(p+1,p+n,comp);
stack[1]=P;
stack[2]=p[1];
for (i=2;i<=n;++i){
while (!isLeft(stack[q-2],p[i],stack[q-1]))q--;
stack[q++]=p[i];
}
q--;
printf("%d\n",q-1);
for (i=2;i<=q;++i)
printf("%lf %lf\n",stack[i].x,stack[i].y);
return 0;
}