Hihocoder 1083 積分：多邊形重心與面積分部計算

題目大意

給定 N (≤8000) 個頂點的簡單多邊形（不自交，無三點共線），計算積分 ∬_P (x + y) dA，結果保留兩位小數。T ≤ 500 測試用例。

數學推導

積分可分解：

∬_P (x + y) dA = ∬_P x dA + ∬_P y dA

由重心公式：

x_G = (∬_P x dA) / Area, y_G = (∬_P y dA) / Area

∴ 積分 = Area × (x_G + y_G)

三角形分解法

固定頂點 0，將多邊形分解為 N-2 個三角形：ΔP₀Pᵢ₋₁Pᵢ (i=2..N-1)。

• 三角形面積（叉積）：Sᵢ = ½ |(Pᵢ₋₁-P₀) × (Pᵢ-P₀)|
• 三角形重心：Gᵢ = (P₀ + Pᵢ₋₁ + Pᵢ) / 3
• 三角形貢獻：Sᵢ × (Gᵢ.x + Gᵢ.y)

代碼實現

double x[8005], y[8005];

int main() {
    int T, n; cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
        
        double total_area = 0, integral = 0;
        for (int i = 2; i < n; ++i) {
            // 向量叉積求有向面積
            double cross = (x[i-1]-x[0])*(y[i]-y[0]) - (y[i-1]-y[0])*(x[i]-x[0]);
            double area = cross / 2.0;
            total_area += area;
            
            // 重心
            double gx = (x[0] + x[i-1] + x[i]) / 3.0;
            double gy = (y[0] + y[i-1] + y[i]) / 3.0;
            
            integral += (gx + gy) * area;
        }
        // 面積可能為負（頂點順序），積分同號
        if (total_area < 0) integral = -integral;
        
        cout << fixed << setprecision(2) << integral << '\n';
    }
}

關鍵點

• 有向面積：叉積保留符號，自動處理頂點順序（順/逆時針）
• 數值穩定：double 足夠，坐標 ≤ 20000，面積 ≤ 1.6e9，積分 ≤ 3.2e13，double 52 位尾數無壓力
• 邊界情況：N=3 時循環不執行，需單獨處理或信任循環邏輯（i=2 只執行一次）

複雜度

• 時間：O(N) 每測試用例，總 O(∑N) ≤ 4×10⁶
• 空間：O(N)

驗證樣例

// 輸入：
2
4
4 -1
-1 4
-6 -1
-1 -6
4
0 0
10 0
10 10
0 10

// 輸出：
-100.00
1000.00