主題
題目連結：
題目意譯：
你被給定一個彼此不重疊且與座標軸對齊的矩形之陣列 rects，其中 rects[i] = [ai, bi, xi, yi] 代表著 (ai, bi) 為第 i 個矩形的左下角，而 (xi, yi) 為第 i 個矩形的右上角。請設計一個演算法來選出一個位於任一個矩形所覆蓋的範圍之中的隨機整數點。一個位於某個矩形的周長上的點是算在矩形的覆蓋範圍中。
任何位於任一個矩形所覆蓋的範圍之中的整數點應有均等的機率被挑到。
注意到一個整數點為一個有整數座標值的點。
實作類別 Solution：
Solution(int[][] rects) 初始化一個物件，其包含著給定的矩形陣列 rects。
int[] pick() 回傳一個隨機整數點 [u, v]，該點位於任一個矩形所覆蓋的範圍之中。
限制：
1 ≦ rects.length ≦ 100
rects[i].length == 4
-10 ^ 9 ≦ ai < xi ≦ 10 ^ 9
-10 ^ 9 ≦ bi < yi ≦ 10 ^ 9
xi - ai ≦ 2000
yi - bi ≦ 2000
所有矩形彼此之間不重疊。
最多呼叫 10 ^ 4 次的 pick。
範例測資：
範例 1：
輸入
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
輸出
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]
解釋
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // return [1, -2]
solution.pick(); // return [1, -1]
solution.pick(); // return [-1, -2]
solution.pick(); // return [-2, -2]
solution.pick(); // return [0, 0]
解題思維：
由於每一個矩形彼此不重疊，而且題目要求的是整數點。因此我們可以為每一個矩形直接先算出各自有幾個整數點在其中。
假設各自有 C1 、 C2 、 C3 、 …… 個整數點，而此時我們可以按照前綴和（Prefix Sum，參見這題）的作法求出以下項次：
P0 = 0、
P1 = C1、
P2 = C1 + C2、
P3 = C1 + C2 + C3、
……
假設所有可能的整數點數量之總和為 S，則我們可以在 0 ～ S - 1 之間隨機挑出一個整數，即按照類似這題的作法。然後接著判斷該整數位於哪個 Pi ～ Pi+1 之間。即可知道該整數「屬於」哪個矩形。
假如現在挑出的整數是 X，且已知其屬於矩形 R（即 Pr ≦ X < Pr+1），則接下來就是看你怎麼決定出矩形中的點。
以範例程式碼為例，將 X 除以 R 的列數來看其位於由下往上的第幾列（索引值從 0 開始數），而其餘數即為由左至右的行數（索引值也是從 0 開始數）。
而接著把列數加到矩形 R 左下角的 Y 座標、行數加到矩形 R 左下角的 X 座標便可以得到我們本次隨機挑出的點。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
