# 497. 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:

1. An integer point is a point that has integer coordinates.
2. A point on the perimeter of a rectangle is included in the space covered by the rectangles.
3. `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.
4. length and width of each rectangle does not exceed `2000`.
5. `1 <= rects.length <= 100`
6. `pick` return a point as an array of integer coordinates `[p_x, p_y]`
7. `pick` is called at most `10000` times.

Example 1:

Input:

``````["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output:
[null,[4,1],[4,1],[3,3]]
``````

Example 2:

``````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.

## # 解题方法

``````class Solution(object):

def __init__(self, rects):
"""
:type rects: List[List[int]]
"""
self.rects = rects
self.N = len(rects)
areas = [(x2 - x1 + 1) * (y2 - y1 + 1) for x1, y1, x2, y2 in rects]
self.preSum = [0] * self.N
self.preSum[0] = areas[0]
for i in range(1, self.N):
self.preSum[i] = self.preSum[i - 1] + areas[i]
self.total = self.preSum[-1]

def pickRect(self):
rand = random.randint(0, self.total - 1)
return bisect.bisect_right(self.preSum, rand)

def pickPoint(self, rect):
x1, y1, x2, y2 = rect
x = random.randint(x1, x2)
y = random.randint(y1, y2)
return x, y

def pick(self):
"""
:rtype: List[int]
"""
rectIndex = self.pickRect()
rect = self.rects[rectIndex]
return self.pickPoint(rect)

# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()
``````

https://blog.csdn.net/fuxuemingzhu/article/details/81807215

## # 日期

2018 年 10 月 16 日 —— 雨后天晴霾散