Random Point in Non-overlapping Rectangles
Given a list of non-overlapping axis-aligned rectangles rects
, write a function pick
which randomly and uniformily picks an integer point in the space covered by the rectangles.
Note:
- An integer point is a point that has integer coordinates.
- A point on the perimeter of a rectangle is included in the space covered by the rectangles.
i
th rectangle =rects[i]
=[x1,y1,x2,y2]
, where[x1, y1]
are the integer coordinates of the bottom-left corner, and[x2, y2]
are the integer coordinates of the top-right corner.- length and width of each rectangle does not exceed
2000
. 1 <= rects.length <= 100
pick
return a point as an array of integer coordinates[p_x, p_y]
pick
is called at most10000
times.
Example 1:
Input: ["Solution","pick","pick","pick","pick","pick"] [[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]] Output: [null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]
Explanation of Input Syntax:
The input is two lists: the subroutines called and their arguments. Solution
's constructor has one argument, the array of rectangles rects
. pick
has no arguments. Arguments are always wrapped with a list, even if there aren't any.
Example 2:
Input: ["Solution","pick","pick","pick"] [[[[1,1,5,5]]],[],[],[]] Output: [null,[4,1],[4,1],[3,3]]
class Solution {
public:
vector<vector<int> > rects;
vector<int> q;
Solution(vector<vector<int>>& rects)
{
int sum=0;
for(auto p:rects)
{
sum+=(p[2]-p[0]+1)*(p[3]-p[1]+1);
q.push_back(sum);
}
this->rects=rects;
}
vector<int> pick() {
int i=lower_bound(q.begin(),q.end(),rand()%q.back()+1)-q.begin();
int d1=rects[i][2]-rects[i][0]+1;
int d2=rects[i][3]-rects[i][1]+1;
int x=rand()%d1;
int y=rand()%d2;
return {rects[i][0]+x,rects[i][1]+y};
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(rects);
* vector<int> param_1 = obj->pick();
*/