主題
題目連結：
題目意譯：
給定一個圓的半徑以及其圓心之位置，實作函式 randPoint 其將產生一個圓中的均勻（Uniform）隨機點。
實作類別 Solution：
Solution(double radius, double x_center, double y_center) 初始化一個物件，有著圓半徑 radius 以及圓心位置 (x_center, y_center) 。
randPoint() 回傳圓中的一個隨機的點。一個位於圓周上的點視為在圓內。答案以陣列形式 [x, y] 回傳。
限制：
0 < radius ≦ 10 ^ 8
-10 ^ 7 ≦ x_center 、 y_center ≦ 10 ^ 7
最多有 3 × 10 ^ 4 次呼叫為 randPoint。
範例測資：
輸入
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
輸出
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]
解釋
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // 回傳 [-0.02493, -0.38077]
solution.randPoint(); // 回傳 [0.82314, 0.38945]
solution.randPoint(); // 回傳 [0.36572, 0.17248]
解題思維：
假設 RAN 為一個介於 0 ～ 1 之間的隨機數（C++ 可能會寫 double(rand()) / RAND_MAX 來得到這樣的 R 值，python 則為 random.random()）。
雖然你可以直接生成一個點為 (x_center + (2RAN - 1) × radius, y_center + (2RAN - 1) × radius) （2RAN - 1 代表著 -1 ～ 1 之間的一個隨機數）然後判斷該點有沒有在圓內。如果在就回傳該點座標；反之就繼續隨機產生另一個點直到在圓內。
這樣依然可以確保圓內的點有著均勻分布的機率會被選到，儘管看似有些點被拋棄了。但是因為整體是均勻分布的，所以就算現在侷限範圍於一圓仍是均勻分布。上述方法稱為棄卻抽樣（Rejection Sampling）。
但是這樣如果運氣不好的話，有機會需要重複挑選相當多次的點才會落在圓內，意即生成單一一個隨機點的最差時間複雜度為 O(∞)。
因此我們可以採取極座標（Polar Coordinate）隨機取點——即標準座標平面上的點 (x, y) 會被改寫為 (dcos(θ), dsin(θ)) ，其中 θ 為向量 (x, y) 與 X 軸之夾角 、 d 為 sqrt(x ^ 2 + y ^ 2)，即點 (x, y) 到原點 (0, 0) 之距離。
所以我們可以改為隨機產生出兩個變數值 L = RAN × radius 、 A = RAN × 2π ，然後套入上面的極座標格式便可以得到一點 (x_center + Lcos(A), y_center + Lsin(A)) 。而此點保證在圓內，不需特別判斷。
但是這樣會有一個大問題，即現在點不再是均勻分布了（儘管看起來應該要是均勻的）。如果我們真的按照上述方式取點，我們會看到：
（上圖的取點數為 5000 個）
而將 L 的值改為 sqrt(RAN) × radius 即可以得到類似以下的均勻分布：
（取點數同樣是 5000 個點）
原因可以從下圖看出：
可以看到，原本 L 之值落在 [0, r] 或是 [r, 2r] 這兩個範圍是均等的，而角度 θ 從 0 度 ～ 360 度（或是弧度 0 ～ 2π）也是均等的機率。
但是圖中兩個同心圓，中間的圓因面積為較小所以只需要較少的點便可以填滿（也就是點密度會較大）；相對的較外層的圓，因為面積大，所以需要較多的點填滿（也就是點密度會較小）。而密度差便造成了機率分布的不均勻（機率的「本質」與密度有著密切關係）。
而密度與距離圓心的距離 r ^ 2 成正比。因此當我們將 RAN 取 sqrt() （即取其平方根），我們便可以抵銷掉 r ^ 2 所帶來的密度差（因為 0 ～ 1 之間的數字取平方根後會更靠近 1，例如 sqrt(0.25) = 0.5）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
