Pagini recente » Cod sursa (job #3150555) | Cod sursa (job #231792) | Cod sursa (job #902045) | Cod sursa (job #230828) | Cod sursa (job #1773325)
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
struct punct
{
double x,y;
};
punct a[120009];
int st[120009],n,m,i,j,k,p=1;
int sgn(punct * a,punct * b,punct * c)
{
return ((a->x*b->y+a->y*c->x+b->x*c->y-c->x*b->y-b->x*a->y-a->x*c->y) < 0);
}
int cmp(const punct &a,const punct & b)
{
if (a.x==b.x)
return (a.y>b.y);
return (a.x<b.x);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=0;i<n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
//qsort(a,n,sizeof(punct),cmp);
sort(a,a+n,cmp);
k=1;
st[k]=0;
st[++k]=1;
for (i=2;i>=0;i+=p)
{
while (k>1 && sgn(&a[st[k-1]],&a[st[k]],&a[i]))
k--;
st[++k]=i;
if (i==n-1) p=-1;
}
printf("%d\n",k-1);
for (i=1;i<k;++i)
printf("%.6lf %.6lf\n",a[st[i]].x,a[st[i]].y);
fclose(stdin);
fclose(stdout);
return 0;
}