# 将树围起来(几何凸包）- HDU 1392

Problem Description

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.

Input

The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank. 多组测试，每个测试第一行是树的数目N，接着N行是树的坐标。 Zero at line for number of trees terminates the input for your program.

N=0表示结束。

Output

The minimal length of the rope. The precision should be 10^-2.

Sample Input

```9
12 7
24 9
30 5
41 9
80 7
50 87
22 9
45 1
50 7
0```

Sample Output

`243.06`

Andrew算法，Graham算法的变种，速度更快稳定性也更好。

1)把P1,P2放入凸包中，凸包中的点使用栈存储，一般的我们取最左边(横坐标最小)的点作为参考点 如果有多个这样的点就取最下面的(纵坐标最小)。

2)从p3开始，当下一个点在凸包当前前进方向（即直线p1p2）左边的时候继续。

3)否则依次删除最近加入凸包的点，直到新点在左边。

```#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long LL;

//定义一个点类型
struct Point {
LL x, y;

Point() {}
Point(LL _x , LL _y): x(_x), y(_y) {}

//重载减法运算
Point operator - (const Point &b) const {
return Point(x - b.x, y - b.y);
}
};

//所有的点
Point points[110];
Point ch[110];

//计算叉积
LL Cross(const Point &a, const Point &b) {
return a.x * b.y - a.y * b.x;
}

bool cmp(const Point &a, const Point &b) {
return (a.x < b.x || (a.x == b.x && a.y < b.y));
}

//Andrew算法，Graham算法的变种，速度更快稳定性也更好。
int Andrew(int size) {
//1.把所有点按照x从小到大进行排序 （x同则y用y进行排序）
sort(points, points + size, cmp);

int m = 0;
//直到碰到最右边的Pn，求出下凸包即凸包的下轮廓
for (int i = 0; i < size; i++) {
//如果叉积小于0，表示p0p2在p0p1的左方向
while (m >= 2 && Cross(ch[m - 1] - ch[m - 2], points[i] - ch[m - 2]) < 0)
m--;

ch[m++] = points[i];
}

int k = m;
//从Pn反过来重复该步骤求出上凸包，合并起来后就是完整的凸包
for (int i = size - 2; i >= 0; i--) {
while (m > k && Cross(ch[m - 1] - ch[m - 2], points[i] - ch[m - 2]) < 0)
m--;

ch[m++] = points[i];
}

return m;
}

double distance(const Point &a, const Point &b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main() {
//freopen("test.txt", "r", stdin);
//输入有多少个点size
int size = 0;
while (~scanf("%d", &size) && size) {
//依次输入这n个点的坐标
for (int i = 0; i < size; i++){
scanf("%lld%lld", &points[i].x, &points[i].y);
}

//如果只有2个点，直接输出距离
if (size == 2) {
printf("%.2f\n", distance(points[0], points[1]));
continue;
}

int cnt = Andrew(size);

//将第cnt个设置为第一个点，也就是最后一个点和第一个点连起来的距离
ch[cnt] = ch[0];

//总距离
double sum = 0;

//依次累计每个点的距离
for (int i = 0; i < cnt; i++)
sum += distance(ch[i], ch[i + 1]);

printf("%.2f\n", sum);
}
return 0;
}```

216 篇文章34 人订阅

0 条评论

## 相关文章

### Tensor

在 TensorFlow 中用 tensor 数据结构来代表所有的数据, 计算图中, 操作间传递的数据都是 tensor。

16720

### tf API 研读2：math

TF API数学计算 tf...... ：math （1）刚开始先给一个运行实例。         tf是基于图（Graph）的计算系统。而图的节点则是由操作（...

81550

14020

### 大过年的，一起来用Seq2Seq来作对联吧！

Seq2Seq全称Sequence to Sequence，在机器翻译、文章摘要等领域有着广泛的应用。其本身很简单，是一个如下图所示的Encoder-Decod...

1.3K80

### Python+numpy实现函数向量化

Python本身对向量操作的支持并不是很好，需要借助列表推导式或函数式编程来实现，例如： >>> import random # 生成随机测试数据 >>> x...

85850

39630

14620

### 有限域(2)——理想和商环

我们上一节介绍了环(ring)、域(field)的概念，并给了一些环、域的实例。比如我们知道整数环、方阵环、有理数域、实数域等。我们知道，域是环的一个种。最...

9220

### Python： numpy总结(3)

21、dot矩阵点积 例子： ll = [[1,2,3],[4,5,6],[7,8,9]]ld = dot(ll,ll) print 'dot:',l...

34340

26610