HDOJ 4454 Stealing a Cake：計算幾何 + 枚舉角度求最短路徑

題目大意

平面上有一圓形蛋糕（圓心 C、半徑 r）和一矩形蟻穴（對頂點 (x1,y1), (x2,y2)）。螞蟻從起點 P 出發，需觸碰蛋糕（任意邊界點）後到達蟻穴（任意邊界點）。蛋糕可穿過。求最短路徑長度。保證起點、蛋糕、蟻穴互不重疊/接觸。

幾何模型：折線路徑 P → Q(蛋糕上) → R(蟻穴上)

路徑長 |PQ| + |QR|。Q 在圓上，R 在矩形邊界上。目標：最小化總長。

解法：枚舉圓上切點角度

圓上點參數化：Q(θ) = C + r*(cosθ, sinθ)，θ ∈ [0, 2π)。對每個 θ：

1. 計算 d1 = |P - Q(θ)|。
2. 計算 d2 = min_{R∈矩形邊界} |Q(θ) - R| = 點到矩形的最短距離。
3. 更新答案 ans = min(ans, d1 + d2)。

點到矩形最短距離

矩形邊平行坐標軸。若點在矩形內（題目保證不在），距離為 0。否則距離為點到 4 條邊線段的最小距離。線段距離公式：投影在線段內取垂直距離，否則取端點距離。

C++ 核心代碼

精度與優化

  
枚舉步數 10000 足夠 2 位小數精度；可用三分法/模擬退火進一步優化。
  
點到線段距離用向量投影避免三角函數，提高速度與穩定性。
  
注意 hypot 防止溢出。