Pagini recente » Cod sursa (job #2662355) | Cod sursa (job #2259909) | Cod sursa (job #2870603) | Cod sursa (job #2790361) | Cod sursa (job #1773194)
#include <bits/stdc++.h>
using namespace std;
struct punct
{
double x,y;
};
punct a[120009];
int st[120009],n,m,i,j,k;
bool 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);
}
bool cmp(punct &a,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);
sort(a,a+n,cmp);
k=1;
st[k]=0;
st[++k]=1;
for (i=2;i<n;++i)
{
while (k>1 && sgn(a[st[k-1]],a[st[k]],a[i]))
k--;
st[++k]=i;
}
for (i=n-1;i>=0;--i)
{
while (k>1 && sgn(a[st[k-1]],a[st[k]],a[i]))
k--;
st[++k]=i;
}
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;
}