ZOJ 3871 Convex Hull：凸包邊界期望面積計算 (極角排序 + 組合數學)

問題描述

給定 N 個點，每個點以概率 1/2 獨立被選中。求選中點集的凸包面積期望值模 998244353。N≤1000。

核心思路：枚舉有向邊作為凸包邊界

凸包面積 = 1/2 Σ (叉積)。對每條有向邊 i→j，計算其作為凸包邊界的概率，乘以其貢獻的有向面積 (叉積/2)，累加得期望面積。

邊為凸包邊界的條件

有向邊 i→j 是凸包邊界 ⇔ 所有其他選中點都在該有向線的**左側** (或線上)。

• 對於固定 i，計算所有其他點相對 i 的極角，排序。
• 複製一份角度 +2π 處理循環。
• 雙指針 r 維護：angle[r] - angle[j] < π 的點都在 i→j 左側。
• 左側點數 = r - j。這些點**必須全不選中** (概率 (1/2)^{左側點數})，而 i,j 必須選中 (概率 1/4)。
• 邊貢獻概率 = (1/4) * (1/2)^{左側點數}。

關鍵代碼框架 (C++)

const int MOD = 998244353;
const int MAXN = 1005;
ll pow2[MAXN]; // 預計算 2^i mod MOD

struct Point { ll x, y; double ang; };
Point p[MAXN], tmp[MAXN*2];

ll cross(Point a, Point b, Point c) { // (b-a) × (c-a)
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

int main() {
    pow2[0]=1;
    for(int i=1;i

關鍵數學細節

模逆元：inv2 = (MOD+1)/2 = 499122177，pow_inv2[k] = inv2^k mod MOD。
有向面積：叉積直接給出有向面積×2，無需除以 2 再乘，最後統一乘 inv2。
極角排序：atan2 計算角度，雙指針掃描半平面。


複雜度分析

時間：O(N² log N) — N 次極角排序 (N log N) + N 次雙指針掃描 (N)。
空間：O(N)。


總結
ZOJ 3871 是「期望凸包面積」的經典解法：將面積期望分解為邊貢獻期望之和，利用極角排序+雙指針計算每條邊為凸包邊界的概率。結合模數算術與預計算冪次，是計算幾何期望問題的標準範式。