# SSL 1720_Surround the Trees_凸包

## 题目描述

There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?
The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.

There are no more than 100 trees.

## 思路

``````#include <stdio.h>
#include <cmath>
#define maxn 10000
#define INF 0x7f7f7f7f
using namespace std;
int x=0,p=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*p;
}
struct arr
{
int x,y;
}e[maxn];
double dist(arr a,arr b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cros(arr a,arr b,arr c)
{
return (a.y-c.y)*(b.x-c.x)-(a.x-c.x)*(b.y-c.y);
}
int main()
{
int n;
while (scanf("%d",&n)&&n!=0)
{
for (int i=1;i<=n;i++)
e[i].intput();
e=(arr){INF,INF};
int t=0;
for (int i=1;i<=n;i++)
if (e[i].x<e[t].x||e[i].x==e[t].x&&e[i].y<e[t].y)
t=i;
double ans=0;
int k=t,p;
do
{
int i=0;
double dis=0;
for (int j=1;j<=n;j++)
if (j!=k)
{
if (i)
p=cros(e[k],e[i],e[j]);
if (p<0||i==0)
dis=dist(e[k],e[j]),i=j;

}
ans+=dis;
k=i;
}
while (t!=k);
if (n==1) ans=0;
printf("%.2lf\n",ans);
}
}
``````

「雪霁融雾月,冰消凝夜雨」