497. 非重叠矩形中的随机点
题目：给定一个由非重叠的轴对齐矩形的数组 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 次。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
这道题类似入门力扣自学笔记53。
但是这道题主要运用了前缀和数组以及二分查找的方法。
代码：
class Solution {
private:
vector> recs;
public:
Solution(vector>& rects)
{
recs = rects;
}
vector pick()
{
int idx = -1, cur = 0, curSum = 0, n = recs.size();
for(int i = 0; i < n; ++i)
{
int x1 = recs[i][0], y1 = recs[i][1], x2 = recs[i][2], y2 = recs[i][3];
cur = (x2-x1+1) * (y2-y1+1);
curSum += cur;
if(rand()%curSum < cur)
idx = i;
}
int x1 = recs[idx][0], y1 = recs[idx][1], x2 = recs[idx][2], y2 = recs[idx][3];
return {x1 + rand()%(x2-x1+1), y1 + rand()%(y2-y1+1)};
}
};
