hihoCoder 1225 向日葵：凸包邊界期望面積 (雙點隨機位置)

問題描述

N 條線段，每條線段兩端點各有兩個可能位置 (向日葵花瓣)。每個端點等概率 (1/2) 選擇兩個位置之一。求最終形成的凸包面積期望。

核心思路：枚舉有向邊 + 概率疊加

與 ZOJ 3871 類似，但每個點有兩個可能位置。對固定有向邊 i→j (此處 i,j 為線段索引)，需考慮四種端點位置組合：

• A[i]→A[j], A[i]→B[j], B[i]→A[j], B[i]→B[j]。

每種組合概率 1/4。對每種組合，計算其他線段端點落在左側的概率分佈 (每個線段有 0,1,2 個端點在左側，概率分別 1/4, 1/2, 1/4)。

算法流程

1. 對每條線段 i 作為起點，收集所有其他線段的兩個端點位置，計算相對極角，排序並複製 +2π。
2. 雙指針掃描維護左側半平面。但左側端點數不再是確定的，而是隨機變量。
3. 用滑動窗口 + 計數器維護：窗口內端點按所屬線段分組計數 C1 (1個端點在左), C2 (2個端點在左)。
4. 窗口對應某條有向邊 i→j 的某種位置組合。若 C1 + 2*C2 == 窗口大小 (無遺漏) 且總線段數匹配，則該邊可能成為凸包邊界。
5. 概率 = (1/4) * (1/2)^{C1} * (1)^{C2} (兩端點都在左側不影響邊界性質，但需扣除概率)。
6. 累加面積貢獻 × 概率。

關鍵代碼片段 (滑動窗口維護 C1, C2)

void add(int seg_id) {
    cnt[seg_id]++;
    if (cnt[seg_id] == 1) C1++;
    else { C1--; C2++; } // 變為 2
}
void del(int seg_id) {
    cnt[seg_id]--;
    if (cnt[seg_id] == 0) C1--;
    else { C2--; C1++; } // 變為 1
}
// 在雙指針循環中：
for (int j=0; j

複雜度分析

時間：O(N² log N) — N 個起點，每次排序 2(N-1) 個端點。
空間：O(N)。


關鍵細節

雙重隨機性：邊本身端點位置隨機 (1/4)，其他端點位置隨機 (左側概率 1/2)。
最終除以 4：代碼中枚舉了所有有向邊 i→j (含 j→i)，每條無向邊算兩次，且邊端點組合已含 1/4，最終需再除以 4 (或開頭乘 1/16)。
數值精度：用 double 存儲角度、面積、概率，最終輸出 %.6lf。


總結
hihoCoder 1225 是 ZOJ 3871 的進階變體：點位置不確定性增加了概率計算的維度。核心仍是「枚舉有向邊 + 極角掃描半平面」，但需維護滑動窗口內線段端點分佈統計 (C1, C2) 來計算組合概率。此類「幾何期望 + 概率組合」問題是高難度計算幾何的典型範式。