自测
复杂度都是 $O(nlogn)$

Graham scan算法 求凸包

基于极角排序求凸包
找到最最下角的点 P；
以P为原点做一次极角排序。
维护以个满足凸性的栈。
因为是极角排序所以常数稍大。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define str string
#define PII pair<ll, ll>
#define fir first
#define sec second
#define siz(s) (ll)(s.size())
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
const int N = 2e5 + 10;
struct Point{
    double x, y;
}P[N];
double operator ^ (Point a, Point b){
    return a.x * b.y - a.y * b.x;
}
Point operator - (Point a, Point b){
    return {a.x - b.x, a.y - b.y}; 
}
vector<Point> a, b;
bool check(Point x, Point y, Point z){
    return ((y - x) ^ (z - y)) <= 0.0;
}
double dist(Point a, Point b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool cmp(Point a, Point b){
    double ans = (a - P[1]) ^ (b - P[1]);
    if(ans > 0) return true;
    if(ans == 0.0 && dist(P[1], a) < dist(P[1], b)) return true;
    return false;
}
int main(){
    int n;
    cin >> n;
    rep(i, 1, n){
        double x, y;
        cin >> P[i].x >> P[i].y;
        if(P[i].x < P[1].x || (P[i].x == P[1].x&&P[i].y < P[1].y)) 
            swap(P[i], P[1]);
    }
    sort(P + 2, P + 1 + n, cmp);
    int idx = 0;
    rep(i, 1, n){
        while(a.size() > 1&&check(*prev(a.end() - 1), a.back(), P[i])) a.pop_back();
        a.push_back(P[i]);
    }
    double res = 0;
    rep(i, 0, siz(a) - 1)
        res += dist(a[i], a[(i + 1)%(siz(a))]);
    printf("%.10lf", res);
}

Andrew 算法

以x为关键字排序。
维护上下凸包
常数较小， 推荐

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define endl '\n'
#define str string
#define PII pair<ll, ll>
#define fir first
#define sec second
#define siz(s) (ll)(s.size())
#define priq priority_queue
#define SPO(n) fixed << setprecision(n)
#define rep(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#define per(i, r, l) for (ll(i) = (r); (i) >= (l); --(i))
#define DBG(n) cout<<"!!! "<<#n<<": "<<n<<'\n'
const int N = 2e5 + 10;
struct Point{
    double x, y;
};
vector<Point> p;
double operator ^ (Point a, Point b){
    return a.x * b.y - a.y * b.x;
}
Point operator - (Point a, Point b){
    return {a.x - b.x, a.y - b.y}; 
}
vector<Point> a, b;
bool check(Point x, Point y, Point z){
    return ((y - x) ^ (z - y)) <= 0.0;
}
double dist(Point a, Point b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main(){
    int n;
    cin >> n;
    rep(i, 1, n){
        double x, y;
        cin >> x >> y;
        p.push_back({x, y});
    }
    sort(p.begin(), p.end(), [&](Point a, Point b){
        if(a.x == b.x) return a.y < b.y;
        return a.x < b.x;
    });
    int idx = 0;
    for(auto x:p){
        while(a.size() > 1&&check(*prev(a.end() - 1), a.back(), x)) a.pop_back();
        a.push_back(x);
    }
    p.pop_back();
    reverse(p.begin(), p.end());
    idx = a.size();
    for(auto x:p){
        while(a.size() > idx&&check(*prev(a.end() - 1), a.back(), x)) a.pop_back();
        a.push_back(x);
    }
    double res = 0;
    rep(i, 0, siz(a) - 1)
        res += dist(a[i], a[(i + 1)%(siz(a))]);
    printf("%.10lf", res);
}

旋转卡壳

ll res = 0;
    int m = a.size();
    a.push_back(a[0]);
    for(int i = 0, j = 1;i < m;i ++){
        while(((a[j] - a[i + 1]) ^ (a[i] - a[i + 1])) < ((a[j + 1] - a[i + 1]) ^ (a[i] - a[i + 1]))){
            j = (j + 1) % m;
            res = max(res, max(dist(a[i], a[j]), dist(a[i + 1], a[j])));
        }
        res = max(res, max(dist(a[i], a[j]), dist(a[i + 1], a[j])));
    }
    a.pop_back();