​LeetCode刷题实战497：非重叠矩形中的随机点

示例 1：
输入: 
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
输出: 
[null,[4,1],[4,1],[3,3]]

示例 2：
输入: 
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
输出: 
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

class Solution {
public:
    vector<vector<int>> _rects;//统计各个矩形
    vector<int> _area;//获得各个矩形对应的面积
    long _sum_area;//总的矩形面积
    Solution(vector<vector<int>>& rects):_rects(rects) {
        _area.reserve(_rects.size());
        _sum_area=0;
        for(vector<int>& rect:_rects){
            _area.push_back((rect[2]-rect[0]+1)*(rect[3]-rect[1]+1));//获得各个矩形的面积
            _sum_area+=_area.back();
        }
    }
    
    vector<int> pick() {
        long sum_area=rand()%_sum_area+1;//将随机数映射到矩形中
        int index=0;
        //找出是第几个矩形
        while(_area[index]<sum_area){
            sum_area-=_area[index];
            ++index;
        }
        vector<int>& cur_rect=_rects[index];
        //对该矩形的高和宽进行区域，映射到矩形内的点
        int x=rand()%(cur_rect[2]-cur_rect[0]+1);
        int y=rand()%(cur_rect[3]-cur_rect[1]+1);
        return {cur_rect[0]+x,cur_rect[1]+y};//加上矩形的左下角，即为坐标
    }
};