Andrew算法思路

1.将点排序：横坐标x为第一关键字，纵坐标y是第二关键字
2.用栈维护：从左到右维护上半部分，从右到左维护下半部分
3.更新：看当前元素，
在栈顶元素的左侧（逆时针）：删掉栈顶元素
在栈顶元素右侧（顺时针）：留下/加入该元素
在栈顶元素延长线：取决于题目要求
（叉积判断点的位置：假设该点在左侧，则栈顶第二的元素与栈顶元素、当前元素构成的三角形向量面积为正，向量P2P1×P2P0 >= 0）
注意：栈底元素 (起点，边界点) 也要再更新一遍

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
//pair支持排序，第一关键字是first，第二关键字是second 
typedef pair<double, double> PDO;
const int N = 100;

int n, stk[N];
PDO q[N];
bool used[N];

double get_dist(PDO a, PDO b){
    double dx = a.first-b.first;
    double dy = a.second-b.second;
    return sqrt(dx*dx+dy*dy);
}
//重载减号 
//PDO operator-(PDO a, PDO b){
//  return {a.first-b.first, a.second-b.second};
//}


//求点积 
double cross(PDO a, PDO b){
    double res = a.first*b.second - a.second*b.first;
    return res;
}
//求面积:叉乘,a,b表示向量 
double area(PDO a, PDO b, PDO c){
    PDO x, y;
    x.first = b.first-a.first;
    x.second = b.second-a.second;
    y.first = c.first-a.first;
    y.second = c.second-a.second;
    return cross(x, y);
}

double andrew()
{
    sort(q, q+n);
    int top=0;
    for(int i=0; i<n; i++){
        //凸包上的点即使在栈中被删除，也不能删掉used中的标记
        while(top>=2 && area(q[stk[top-1]], q[stk[top]], q[i])<=0){
            if(area(q[stk[top-1]], q[stk[top]], q[i])<0)
                used[stk[top--]] = false;
            else top--;
        }
        used[i] = true;
        stk[++top] = i;
    }
    used[0] = false;
    for(int i=n-1; i>=0; i--){
        if(used[i]) continue;
        while(top>=2 && area(q[stk[top-1]], q[stk[top]], q[i])<=0){
            top--;
        }
        stk[++top] = i;
    }

    //有top个点，就有top-1条边，刚好枚举相邻两个点之间的边长 
    double res=0;
    for(int i=2; i<=top; i++){
        res += get_dist(q[stk[i-1]], q[stk[i]]);
    }
    return res;
}
int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%lf%lf", &q[i].first, &q[i].second);
    }
    double res = andrew();
    printf("%.2lf\n", res);
    return 0;
}