将树围起来(几何凸包）- HDU 1392
几何凸包：
在二维欧几里得空间中，凸包可想象为一条刚好包著所有点的橡皮圈。如下图所示。计算凸包也就是求得外围（蓝线上）的那些点。
数学上有严格的证明，如下：
在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。
凸包的算法可以算是计算几何中最基础的算法之一了。寻找凸包的算法有很多种，Graham算法是一种十分简单高效的二维凸包算法，能够在O(nlogn)的时间内找到凸包。
寻找凸包算法涉及到向量的叉乘，上一篇几何文章提到了，可以再复习下。如下图：
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.
不会超过100棵树。
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.
精确到小数点2位。
Sample Input
9
12 7
24 9
30 5
41 9
80 7
50 87
22 9
45 1
50 7
0Sample Output
243.06这是一个计算几何凸包的题目，直接用凸包算法计算即可。
解题思路：
Andrew算法，Graham算法的变种，速度更快稳定性也更好。
1)把P1,P2放入凸包中，凸包中的点使用栈存储，一般的我们取最左边(横坐标最小)的点作为参考点 如果有多个这样的点就取最下面的(纵坐标最小)。
2)从p3开始，当下一个点在凸包当前前进方向（即直线p1p2）左边的时候继续。
3)否则依次删除最近加入凸包的点，直到新点在左边。
源代码：G++
#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;
}