Medium

478. Generate Random Point in a Circle

mathgeometryrejection-samplingrandomized

解題說明

Generate Random Point in a Circle

題目描述：給定一個圓的半徑 radius 和圓心座標 (x_center, y_center)，實作一個函式 randPoint() 在圓內均勻隨機生成一個點。

解題思路：最直觀的方法是拒絕採樣（Rejection Sampling）：在包圍圓的正方形內均勻隨機生成點，若該點落在圓內則接受，否則拒絕並重新生成。正方形面積為 (2r)^2 = 4r^2，圓面積為 pi*r^2，接受率約為 pi/4 ≈ 78.5%，因此期望只需約 1.27 次採樣。這種方法簡單且不涉及三角函式計算。

C++ 解法

複雜度分析

時間複雜度：O(1) 期望 — 每次呼叫期望採樣約 1.27 次（4/pi），為常數時間。

空間複雜度：O(1) — 僅使用常數個變數。

虛擬碼

1. Constructor: store radius r, center (cx, cy)
2. randPoint():
   a. Loop:
      - Generate random x in [cx - r, cx + r]
      - Generate random y in [cy - r, cy + r]
      - If (x - cx)^2 + (y - cy)^2 <= r^2, return [x, y]
      - Else reject and repeat

其他解法

極座標法 O(1)：隨機生成角度 theta 在 [0, 2pi)，半徑 rr = r * sqrt(random(0,1))。轉換為直角座標 (cx + rrcos(theta), cy + rr*sin(theta))。注意半徑需取 sqrt 以確保均勻分佈（因為面積與半徑的平方成正比）。無需拒絕採樣但需要三角函式。

逆變換採樣：直接推導 CDF 的逆函式，分別生成半徑和角度。數學上等價於極座標法，但從概率論角度更嚴謹。

延伸思考

為什麼極座標法中半徑要取 sqrt(random()) 而不是直接用 random()*r？
如果要在圓環（annulus）內均勻取點，該如何修改？
拒絕採樣法的最壞情況時間複雜度是什麼？在實務中會是問題嗎？

Generate Random Point in a Circle — CaffeCode