给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。

    在给定的矩形覆盖的空间内的任何整数点都有可能被返回。

    请注意 ，整数点是具有整数坐标的点。

    实现 Solution 类:

    Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
    int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。

    示例 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(); // 返回 [1, -2]
    solution.pick(); // 返回 [1, -1]
    solution.pick(); // 返回 [-1, -2]
    solution.pick(); // 返回 [-2, -2]
    solution.pick(); // 返回 [0, 0]

    提示：

    1 <= rects.length <= 100
    rects[i].length == 4
    -109 <= ai < xi <= 109
    -109 <= bi < yi <= 109
    xi - ai <= 2000
    yi - bi <= 2000
    所有的矩形不重叠。
    pick 最多被调用 104 次。

    1. class Solution {
    2.     /**
    3.     前缀和 + 二分
    4.     sum[i]表示前i个rs面积，先对面积进行随机，然后运用二分找到是哪个rs[i],再在矩形里面随机坐标
    5.      */
    6.     int[] sum;
    7.     int[][] rs;
    8.     int n;
    9.     Random random = new Random();
    10.     public Solution(int[][] rects) {
    11.         n = rects.length;
    12.         rs = rects;
    13.         sum = new int[n + 1];
    14.         for (int i = 1; i <= n; ++i) 
    15.             sum[i] = sum[i - 1] + (rs[i - 1][2] - rs[i - 1][0] + 1) * (rs[i - 1][3] - rs[i - 1][1] + 1);
    16.     }
    18.     public int[] pick() {
    19.         //先二分是哪个矩形
    20.         int cur = random.nextInt(sum[n]) + 1;
    21.         int l = 0, r = n;
    22.         while (l < r) {
    23.             int mid = l + r >> 1;
    24.             if (sum[mid] >= cur) r = mid;
    25.             else l = mid + 1;
    26.         }
    27.         int[] t = rs[l - 1];
    28.         int x = random.nextInt(t[2] - t[0] + 1) + t[0];
    29.         int y = random.nextInt(t[3] - t[1] + 1) + t[1];
    30.         return new int[]{x, y};
    31.     }
    32. }
    34. /**
    35.  * Your Solution object will be instantiated and called as such:
    36.  * Solution obj = new Solution(rects);
    37.  * int[] param_1 = obj.pick();
    38.  */