<p>You are given an array of non-overlapping axis-aligned rectangles <code>rects</code> where <code>rects[i] = [a<sub>i</sub>, b<sub>i</sub>, x<sub>i</sub>, y<sub>i</sub>]</code> indicates that <code>(a<sub>i</sub>, b<sub>i</sub>)</code> is the bottom-left corner point of the <code>i<sup>th</sup></code> rectangle and <code>(x<sub>i</sub>, y<sub>i</sub>)</code> is the top-right corner point of the <code>i<sup>th</sup></code> rectangle. Design an algorithm to pick a random integer point inside the space covered by one of the given rectangles. A point on the perimeter of a rectangle is included in the space covered by the rectangle.</p>

<p>Any integer point inside the space covered by one of the given rectangles should be equally likely to be returned.</p>

<p><strong>Note</strong> that an integer point is a point that has integer coordinates.</p>

<p>Implement the <code>Solution</code> class:</p>

<ul>
	<li><code>Solution(int[][] rects)</code> Initializes the object with the given rectangles <code>rects</code>.</li>
	<li><code>int[] pick()</code> Returns a random integer point <code>[u, v]</code> inside the space covered by one of the given rectangles.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/24/lc-pickrandomrec.jpg" style="width: 419px; height: 539px;" />
<pre>
<strong>Input</strong>
[&quot;Solution&quot;, &quot;pick&quot;, &quot;pick&quot;, &quot;pick&quot;, &quot;pick&quot;, &quot;pick&quot;]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
<strong>Output</strong>
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

<strong>Explanation</strong>
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // return [1, -2]
solution.pick(); // return [1, -1]
solution.pick(); // return [-1, -2]
solution.pick(); // return [-2, -2]
solution.pick(); // return [0, 0]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rects.length &lt;= 100</code></li>
	<li><code>rects[i].length == 4</code></li>
	<li><code>-10<sup>9</sup> &lt;= a<sub>i</sub> &lt; x<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= b<sub>i</sub> &lt; y<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>x<sub>i</sub> - a<sub>i</sub> &lt;= 2000</code></li>
	<li><code>y<sub>i</sub> - b<sub>i</sub> &lt;= 2000</code></li>
	<li>All the rectangles do not overlap.</li>
	<li>At most <code>10<sup>4</sup></code> calls will be made to <code>pick</code>.</li>
</ul>

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.areas = [self.get_area(rect) for rect in rects]
        self.prefix_array = self.prefix_sum(self.areas)
    
    def get_area(self, rect: List[int]) -> int:
        a, b, x, y = rect
        w = (x - a) + 1
        h = (y - b) + 1
        area = w * h

        return area
    
    def prefix_sum(self, areas: List[int]) -> List[int]:
        prefix_array = [0] * (len(areas) + 1)
        for i in range(len(areas)):
            prefix_array[i + 1] = prefix_array[i] + areas[i]
        
        return prefix_array
    
    def get_coord(self, rect: List[int], offset: int) -> List[int]:
        a, b, x, y = rect
        w = (x - a) + 1

        c_x = a + (offset % w)
        c_y = b + math.floor(offset / w)

        return [c_x, c_y]
    
    # Not a binary search but I'm fucking tired lol.
    def binary_search_rect(self, target: int) -> int:
        result = 0

        for i in range(1, len(self.prefix_array)):
            s = self.prefix_array[i]

            if target < s:
                result = i
                break
        
        return result

    def pick(self) -> List[int]:
        # 0 <= seed < |S|, |S| := total area
        seed = random.randint(0, self.prefix_array[-1] - 1)
        # index+1 of rectangle containing coordinate
        i_rect = self.binary_search_rect(seed)
        # index of rectangle for coordinate
        rect = self.rects[i_rect - 1]
        # offset inside rectangle
        offset = seed - self.prefix_array[i_rect - 1]
        # coordinate wrt offset
        coord = self.get_coord(rect, offset)

        return coord
        


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