day-144.cpp

/*
  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. ith 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 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.

*/

// O(logN) solution
class Solution {
   public:
    int numPoints;
    vector<int> rectsCumil;
    vector<vector<int>> rects;
    Solution(vector<vector<int>>& rects) {
        numPoints = 0;
        this->rects = rects;
        for (vector<int> rect : rects) {
            numPoints += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            rectsCumil.push_back(numPoints);
        }
    }

    vector<int> pick() {
        int pointIndex = rand() % numPoints;
        int low = 0;
        int high = rects.size() - 1;

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (rectsCumil[mid] <= pointIndex)
                low = mid + 1;
            else
                high = mid;
        }

        vector<int>& rect = rects[low];
        int xPoint = rect[2] - rect[0] + 1;
        int yPoint = rect[3] - rect[1] + 1;

        int pointInRect = xPoint * yPoint;
        int pointStart = rectsCumil[low] - pointInRect;

        int offset = pointIndex - pointStart;

        return {rect[0] + offset % xPoint, rect[1] + offset / xPoint};
    }
};