Pagini recente » Cod sursa (job #892853) | Cod sursa (job #1254103) | Cod sursa (job #2848425) | Cod sursa (job #753472) | Cod sursa (job #2156072)
#include <cstdio>
#include <algorithm>
using namespace std;
struct pct{double x;double y;};
pct v[120002],st[120002],dr[120002],sol[120002];
double aria(pct a,pct b,pct p)
{
return a.x*b.y+b.x*p.y+p.x*a.y-b.y*p.x-p.y*a.x-a.y*b.x;
}
bool cmp(pct a,pct b)
{
return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,nrs=0,nrd=0,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
v[i].x+=1000000000;
v[i].y+=1000000000;
}
sort(&v[1],&v[n+1],cmp);
sol[1]=v[1];
for(i=2;i<=n;i++)
{
if(aria(v[1],v[n],v[i])<=0)
dr[++nrd]=v[i];
else st[++nrs]=v[i];
}
sol[2]=dr[1];
k=2;
for(i=2;i<=nrd;i++)
{
if(aria(sol[k-1],sol[k],dr[i])<0)
sol[k]=dr[i];
else sol[++k]=dr[i];
}
sol[++k]=st[nrs];
for(i=nrs-1;i>=1;i--)
{
if(aria(sol[k],sol[k-1],st[i])>0)
sol[k]=st[i];
else sol[++k]=st[i];
}
printf("%d\n",k);
for(i=1;i<=k;i++)
printf("%lf %lf\n",sol[i].x-1000000000,sol[i].y-1000000000);
return 0;
}