Pagini recente » Cod sursa (job #1894045) | Cod sursa (job #2926248) | Cod sursa (job #2872289) | Cod sursa (job #2640084) | Cod sursa (job #1523832)
#include <cstdio>
#include <algorithm>
using namespace std;
#define eps 0.0000000001
int n,i,u,v[120004];
double st[120004];
struct andreea
{
int x,y;
}a[120004];
double modul(double xx)
{
if(xx<0)return xx;
else return -xx;
}
bool cmp(andreea a, andreea b)
{
if(modul(a.x-b.x)<eps&&a.x<b.x)return 1;
else if(modul(a.x-b.x)>eps&&a.y<b.y)return 1;
return 0;
}
double aria(andreea m, andreea n, andreea p)
{
return (double)m.x*n.y+n.x*p.y+p.x*m.y-n.y*p.x-p.y*m.x-m.y*n.x;
}
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);
u=2;
st[1]=1;
st[2]=2;
v[1]=1;
v[2]=1;
for(i=3;i<=n;i++)
{
if(v[i]==0)
{
while(u>=2&& aria(a[st[u-1]], a[st[u]], a[i]) <eps)
{
v[st[u]]=0;
u--;
}
u++;
st[u]=i;
v[i]=1;
}
}
for(i=n;i>=1;i++)
{
if(v[i]==0)
{
while(u>=2&& aria(a[st[u-1]], a[st[u]], a[i]) <eps)
{
v[st[u]]=0;
u--;
}
u++;
st[u]=i;
v[i]=1;
}
}
printf("%d\n",u);
for(i=1;i<=u;i++)
{
printf("%.6lf %.6lf",a[st[i]].x, a[st[i]].y);
}
return 0;
}