题意：给一堆二维的点，问你最少用多少距离能把这些点都围起来

思路：

凸包：

我们先找到所有点中最左下角的点p1，这个点绝对在凸包上。接下来对剩余点按照相对p1的角度升序排序，角度一样按距离升序排序。因为凸包有一个特点，从最左下逆时针走，所有线都在当前这条向量的左边，根据这个特点我们进行判断。我们从栈顶拿出两个点s[top-1]，s[top]，所以如果s[top-1] -> p[i] 在 s[top-1] -> s[top] 右边，那么s[top]就不是凸包上一点，就这样一直判断下去。判断左右可以用叉乘。

参考：

模板（考虑n <= 2）：

struct node{    double x, y;}p[maxn], s[maxn];int n, top;double dis(node a, node b){    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}bool cmp(node a, node b){    double A = atan2((a.y - p[1].y), (a.x - p[1].x));    double B = atan2((b.y - p[1].y), (b.x - p[1].x));    if(A != B) return A < B;    else{        return dis(a, p[1]) < dis(b, p[1]);    }}double cross(node a, node b, node c){   //(a->b)X(a->c)    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);}void solve(){    int pos = 1;    for(int i = 2; i <= n; i++){        if(p[i].y < p[pos].y || (p[i].y == p[pos].y && p[i].x < p[pos].x)){            pos = i;        }    }    swap(p[1], p[pos]);    sort(p + 2, p + n + 1, cmp);    s[0] = p[1], s[1] = p[2];    top = 1;    for(int i = 3; i <= n; i++){        while(top >= 1 && cross(s[top - 1], p[i], s[top]) >= 0){ //向右转出栈            top--;        }        s[++top] = p[i];    }}

 

代码：

#include
     
      #include