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

#include <cstdlib> 

class Solution {
public:
    bool do_log = true;
    bool do_log_rect_formation = true;
    long total_points_{0};
    vector<vector<int>> rects_;
    Solution(vector<vector<int>>& rects) : rects_(rects) {
        int rect_index = 0;
        for (const vector<int>& curr_rect : rects) {
            const int& rect_low_x = curr_rect[0];
            const int& rect_low_y = curr_rect[1];
            const int& rect_high_x = curr_rect[2];
            const int& rect_high_y = curr_rect[3];
            const long x_points = rect_high_x - rect_low_x;
            const long y_points = rect_high_y - rect_low_y;
            const long tot_points = (x_points + 1) * (y_points + 1);
            total_points_ += tot_points;
            if (do_log_rect_formation && do_log) {
                cout << "rect index: " << rect_index << " | total_points: " << tot_points << "\n";
                cout << "x_points: " << x_points << " | y_points: " << y_points << "\n";
                rect_index++;
            }
        }   
        if (do_log) {
            cout << "Total Points = " << total_points_ << "\n";
        }
    }
    
    vector<int> pick() {
        int lb = 0, ub = total_points_ - 1; 
        // This program will create some sequence of random 
        // numbers on every program run within range lb to ub 
        const int rand_index = (rand() % (ub - lb + 1)) + lb;
        cout << "rand_index: " << rand_index << "\n";
        //return valid_points[rand_index];
        int curr_index = rand_index;
        int curr_rect_index = 0;
        while (curr_rect_index < rects_.size()) {
            const vector<int>& curr_rect = rects_[curr_rect_index];
            const int& rect_low_x = curr_rect[0];
            const int& rect_low_y = curr_rect[1];
            const int& rect_high_x = curr_rect[2];
            const int& rect_high_y = curr_rect[3];
            const long x_points = rect_high_x - rect_low_x;
            const long y_points = rect_high_y - rect_low_y;
            const long tot_points = (x_points + 1) * (y_points + 1);
            if (curr_index >= tot_points) {
                curr_index -= tot_points;
                ++curr_rect_index;
                continue;
            } else {
                break;
            }
        }
        const vector<int>& curr_rect = rects_[curr_rect_index];
        const int& rect_low_x = curr_rect[0];
        const int& rect_low_y = curr_rect[1];
        const int& rect_high_x = curr_rect[2];
        const int& rect_high_y = curr_rect[3];
        const int x_points = rect_high_x - rect_low_x + 1;
        const int y_points = rect_high_y - rect_low_y + 1;
        cout << "curr_index: " << curr_index << " | curr_rect_index: " << curr_rect_index << "\n";
        const int curr_y = floor(curr_index / (x_points));
        int curr_x = curr_index - (curr_y * x_points);
        // if (curr_y == 0) {
        //     curr_x--;
        // }
        cout << "curr_x: " << curr_x << " | curr_y: " << curr_y << "\n";
        cout << "calc_x: " << curr_x + rect_low_x << " | calc_y: " << curr_y + rect_low_y << "\n";
        return {curr_x + rect_low_x, curr_y + rect_low_y};
        //return {((curr_x + 1) % (x_points - 1)) + rect_low_x, ((curr_y + 1) % (y_points - 1)) + rect_low_y};
        //return {((curr_x + 1) % x_points) + rect_low_x, curr_y + rect_low_y};
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(rects);
 * vector<int> param_1 = obj->pick();
 */
71800