Pagini recente » Cod sursa (job #2213652) | Cod sursa (job #2898044) | template/preoni-2007/footer | Cod sursa (job #3277176) | Cod sursa (job #2019041)
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int nmax=120005;
const double eps=1e-12;
int n,m,top;
struct point
{
double x,y;
}punct[nmax];
int st[nmax];
inline int cp(point p1,point p2,point p3)
{
return (p2.x-p1.x)*(p3.y-p2.y) - (p2.y-p1.y)*(p3.x-p2.x);
}
inline bool cmp(const point &p1, const point &p2)
{
if(fabs(p1.x - p2.x) >= eps)
return p2.x - p1.x > eps;
return p2.y - p1.y > eps;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i,j;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%lf%lf",&punct[i].x,&punct[i].y);
sort(punct+1,punct+n+1,cmp);
st[++top]=1;
st[++top]=2;
for(i=3;i<=n;++i)
{
while(top > 1 && cp(punct[st[top-1]],punct[st[top]],punct[i]) <=-eps)
--top;
st[++top]=i;
}
for(i=n-1;i;--i)
{
while(top > 1 && cp(punct[st[top-1]],punct[st[top]],punct[i]) <=-eps)
--top;
st[++top]=i;
}
printf("%d\n",top-1);
for(i=1;i<top;++i)
printf("%lf %lf\n",punct[st[i]].x,punct[st[i]].y);
return 0;
}