Pagini recente » Cod sursa (job #2587658) | Cod sursa (job #2780387) | Cod sursa (job #76375) | Cod sursa (job #433693) | Cod sursa (job #1523841)
#include<cstdio>
#include<algorithm>
#define eps 0.00000000001
using namespace std;
int n,i,nr,ap[120004],st[120004];
struct pct
{
double x,y;
}a[120004];
double mod(double x)
{
if(x<0)return -x;
return x;
}
bool egal(double x,double y)
{
return mod(x-y)<=eps;
}
bool cmp(pct x,pct y)
{
if(egal(x.x,y.x))return x.y<y.y;
return x.x<y.x;
}
double det(pct x,pct y,pct z)
{
return (double)x.x*y.y + z.x*x.y + y.x*z.y - y.y*z.x - x.y*y.x - x.x*z.y;
}
void elim(int i)
{
while(nr>=2&& det ( a[ st[nr-1] ] ,a[st[nr]],a[st[i]])<eps)
{
ap[st[nr]]=0;
nr--;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf %lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
st[1]=1;
st[2]=2;
ap[2]=1;
nr=2;
for(i=3;i<=n;i++)
{
elim(i);
nr++;
st[nr]=i;
ap[i]=1;
}
for(i=n;i>1;i--)
if(ap[i]==0)
{
elim(i);
nr++;
st[nr]=i;
ap[i]=1;
}
elim(1);
printf("%d\n",nr);
for(i=1;i<=nr;i++)
printf("%.6lf %.6lf",a[st[i]].x,a[st[i]].y);
return 0;
}