Điểm ngẫu nhiên trong hình chữ nhật không giao nhau (Random Point in Non-overlapping Rectangles) trong C++

Cho danh sách hình chữ nhật trục tọa độ không giao nhau rects[i] = [x1,y1,x2,y2]. Hàm pick() trả về điểm nguyên ngẫu nhiên đều trong vùng bao phủ.

Thuật toán (Prefix Sum Area + Binary Search)

1. Tính diện tích mỗi HCN: (x2-x1+1)*(y2-y1+1). Xây mảng prefix sum area.
2. pick(): random randArea trong [1, totalArea]. Binary search tìm HCN chứa điểm.
3. Trong HCN đó, random offset dx, dy và trả về (x1+dx, y1+dy).

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    vector area;
    vector> rect;
    int sum=0;
public:
    Solution(vector>& rects) {
        rect = rects;
        for (auto& r : rects) {
            int x1=r[0], y1=r[1], x2=r[2], y2=r[3];
            int a = (abs(x2-x1)+1) * (abs(y2-y1)+1);
            sum += a;
            area.push_back(sum);
        }
    }
    vector pick() {
        int randArea = rand() % sum + 1;
        int i = lower_bound(area.begin(), area.end(), randArea) - area.begin();
        int dx = rand() % (abs(rect[i][0]-rect[i][2])+1);
        int dy = rand() % (abs(rect[i][1]-rect[i][3])+1);
        return {rect[i][0]+dx, rect[i][1]+dy};
    }
};

Ví dụ

Input: [[1,1,5,5]], pick 3 lần → các điểm ngẫu nhiên trong HCN.