UVA 11177 凸多邊形與圓相交面積：二分搜尋 + 幾何分解

題目大意

給定一個凸 n 邊形（按順/逆時針給出頂點）與以原點為圓心的圓，求最小半徑 R，使得圓與多邊形的相交面積 ≥ 給定值 S。
約束：n ≤ 50，多測資，以 n = 0 結束。

核心思路：單調性 + 二分答案

隨著半徑 r 增大，相交面積 Area(r) 單調不減。因此可對 r 在 [0, 1e9] 區間二分，每次判斷 Area(mid) 是否達標。

單次面積計算：邊與圓的關係分類

將凸多邊形分解為 n 個以原點為頂點、邊 P[i]P[i+1] 為底的三角形（P[n]=P[0]）。對每條邊，根據兩端點與圓的位置關係，相交區域僅有四種形態：

關鍵子程式：

• SegmentCircleIntersection：解一元二次方程求線段與圓交點，並用 OnSegment 判斷交點是否落在線段上（原碼註釋指出此處易錯）。
• FanArea：扇形面積 0.5 * r² * θ，其中 θ = Angle(v1, v2)。
• GetCommonArea：綜合上述情形回傳單邊貢獻。

精度與工程細節

• 統一使用 double，比較函數 dcmp(x) 以 eps = 1e-9 容差處理浮點誤差。
• 二分終止條件 dcmp(r - l) > 0，輸出 %.2lf 保留兩位小數。
• 原碼中 OnSegment 用 Dot(p1-p, p2-p) ≤ 0 判斷點 p 是否在線段 p1p2 上，實測正確但直觀性較差，建議改用投影參數 t ∈ [0,1] 判斷。

完整參考代碼（關鍵片段）

double GetCommonArea(Point p1, Point p2, Point p3, Circle C) {
    int in2 = isPointInCircle(p2, C), in3 = isPointInCircle(p3, C);
    Point sol[2]; int num;
    SegmentCircleIntersection(p2, p3, C, sol, num);
    if (in2 + in3 == 2) return fabs(Cross(p2-p1, p3-p1)) * 0.5;
    if (in2 + in3 == 1) {
        if (in2) return FanArea(C, p3-p1, sol[0]-p1) + fabs(Cross(p2-p1, sol[0]-p1))*0.5;
        else     return FanArea(C, p2-p1, sol[0]-p1) + fabs(Cross(p3-p1, sol[0]-p1))*0.5;
    }
    if (num == 2) return FanArea(C, p2-p1, sol[0]-p1) + fabs(Cross(sol[0]-p1, sol[1]-p1))*0.5 + FanArea(C, p3-p1, sol[1]-p1);
    return FanArea(C, p2-p1, p3-p1);
}

總結

本題將「凸多邊形與圓相交面積」拆解為「單邊貢獻求和」，配合二分搜尋半徑，是計算幾何中「分治 + 數值方法」的經典範例。實作時需特別注意交點判斷與浮點比較的健壯性。