HDOJ 2202 最大三角形：凸包 + 旋轉卡殼算法

問題描述

給定平面 n (≤50,000) 個點，求由其任三點組成的最大三角形面積，保留兩位小數。

算法流程

1. 求凸包：Andrew 算法 O(n log n)，得到凸包頂點序列（逆時針）
2. 旋轉卡殼：固定點 i，雙指針 j,k 維護以 i 為一頂點的最大三角形

旋轉卡殼核心邏輯

對固定 i，初始 j=i+1, k=j+1。移動 j 時，k 只單向移動（不回退），利用凸包凸性保證面積單峰性。判斷條件：
cross(P[i]-P[j], P[(k+1)%m]-P[k]) < 0 時 k 前進。
每次更新答案 area2(P[i],P[j],P[k])（兩倍面積，避免浮點）。

完整代碼

#include <bits/stdc++.h>
using namespace std;
struct Point { double x, y; };
double cross(Point a, Point b) { return a.x*b.y - a.y*b.x; }
double area2(Point a, Point b, Point c) { return abs(cross(b-a, c-a)); }

vector<Point> convexHull(vector<Point>& p) {
    sort(p.begin(), p.end(), [](Point a, Point b){ return a.x!=b.x ? a.x1 && cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) --m;
        ch[m++] = p[i];
    }
    int k = m;
    for (int i=n-2; i>=0; --i) {
        while (m>k && cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) --m;
        ch[m++] = p[i];
    }
    if (n>1) --m;
    ch.resize(m);
    return ch;
}

double rotatingCalipers(vector<Point>& ch) {
    int m = ch.size();
    if (m < 3) return 0;
    double ans = 0;
    for (int i=0; i> n) {
        vector<Point> p(n);
        for (int i=0; i> p[i].x >> p[i].y;
        auto ch = convexHull(p);
        printf("%.2f\n", rotatingCalipers(ch) / 2.0);
    }
    return 0;
}

複雜度

• 凸包：O(n log n)
• 旋轉卡殼：O(m) (m 為凸包點數，m ≤ n)
• 總計：O(n log n)，n=50,000 極快

關鍵技巧

1. 凸包去重：unique 配合自定義比較
2. 面積用叉積絕對值，避免浮點誤差
3. 旋轉卡殼雙指針單向移動，總步數 O(m)
4. 輸出保留兩位小數：printf("%.2f\n", area/2)

此題是「凸包上最遠點對/最大三角形」的經典應用，掌握旋轉卡殼模板可解決一系列凸包極值問題。