Pagini recente » Cod sursa (job #2683383) | Cod sursa (job #2004350) | Cod sursa (job #2006649) | Cod sursa (job #1964964) | Cod sursa (job #2019033)
#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],st[nmax<<1];
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("infasuratoareconvexa.in","r",stdin);
freopen("infasuratoareconvexa.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]=punct[1];
st[++top]=punct[2];
for(i=3;i<=n;++i)
{
while(top > 1 && cp(st[top-1],st[top],punct[i]) <=-eps)
--top;
st[++top]=punct[i];
}
for(i=n-1;i;--i)
{
while(top>1 && cp(st[top-1] , st[top] ,punct[i]) <=-eps)
--top;
st[++top]=punct[i];
}
printf("%d\n",top-1);
for(i=1;i<top;++i)
printf("%lf %lf\n",st[i].x,st[i].y);
return 0;
}