BZOJ 1132 三角形面積和：極角排序 + 前綴和優化

BZOJ 1132 三角形面積和：極角排序 + 前綴和優化

給定平面 n ≤ 3000 個點，求任意三點組成的三角形面積和。暴力 O(n³) 超時，需 O(n² log n)。

核心思路

枚舉一點 O 為原點，將其他點按極角（或斜率）排序。對於固定向量 OA，與所有極角更大的向量 OB 組成的三角形面積為叉積 |OA × OB|/2。因排序保證叉積非負，可去絕對值。
面積和 = Σ (x_A * Σ y_B - y_A * Σ x_B)，利用前綴和 O(1) 獲得 Σ x_B, Σ y_B。單點處理 O(n log n)，總 O(n² log n)。

代碼關鍵部分

inline long long Calc(int p, int cnt) {
    // 以 point[p] 為原點，複製後續點並平移
    for (int i = 1; i <= cnt; ++i) {
        temp[i] = point[p+i] - point[p];
        temp[i].slope = temp[i].x ? (double)temp[i].y / temp[i].x : INF;
    }
    sort(temp+1, temp+cnt+1, cmp); // 按極角排序
    // 反向構建前綴和
    for (int i = cnt; i; --i) {
        sum_x[i] = sum_x[i+1] + temp[i].x;
        sum_y[i] = sum_y[i+1] + temp[i].y;
    }
    long long re = 0;
    for (int i = 1; i < cnt; ++i) {
        re += temp[i].x * sum_y[i+1];
        re -= temp[i].y * sum_x[i+1];
    }
    return re; // 實際為 2 * 面積和
}

最終輸出

總和 ans 為 2 * 面積和，輸出 ans/2 及小數部分（.0 或 .5）。