Random Point in Non-overlapping Rectangles สุ่มจุดในสี่เหลี่ยมไม่ทับซ้อนใน C++

ให้ลิสต์สี่เหลี่ยมผืนผ้าไม่ทับซ้อน rects[i] = [x1,y1,x2,y2] (มุมซ้ายล่างและขวาบน) เขียนฟังก์ชัน pick() สุ่มจุดจำนวนเต็มในพื้นที่ที่สี่เหลี่ยมครอบคลุมอย่างสม่ำเสมอ

จุดบนเส้นรอบรูปถือว่าอยู่ในพื้นที่

วิธีแก้ปัญหา (Weighted Random Selection)

1. คำนวณพื้นที่แต่ละสี่เหลี่ยม: area = (x2-x1+1) × (y2-y1+1)
2. สร้าง prefix sum ของพื้นที่
3. pick():
   • สุ่มพื้นที่ randArea ∈ [1, total_area]
   • หาสี่เหลี่ยมที่ randArea อยู่ (binary search หรือ linear scan)
   • สุ่ม x offset และ y offset ภายในสี่เหลี่ยมนั้น
   • คืน {x1 + dx, y1 + dy}

ตัวอย่างโค้ด C++

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> area;
    vector<vector<int>> rect;
    int sum;
    
    Solution(vector<vector<int>>& rects) {
        rect = rects;
        sum = 0;
        for (int i = 0; i < rects.size(); i++) {
            int x1 = rects[i][0], y1 = rects[i][1];
            int x2 = rects[i][2], y2 = rects[i][3];
            int temp = (abs(x2 - x1) + 1) * (abs(y2 - y1) + 1);
            sum += temp;
            area.push_back(sum);
        }
    }
    
    vector<int> pick() {
        int randArea = rand() % sum + 1;
        int i = 0;
        for (; i < area.size(); i++) if (randArea <= area[i]) break;
        int dist_x = rand() % (abs(rect[i][0] - rect[i][2]) + 1);
        int dist_y = rand() % (abs(rect[i][1] - rect[i][3]) + 1);
        return {dist_x + rect[i][0], dist_y + rect[i][1]};
    }
};

int main() {
    vector<vector<int>> v = {{1, 1, 5, 5}};
    Solution ob(v);
    for (int i = 0; i < 3; i++) print_vector(ob.pick());
    return 0;
}

Input

["Solution","pick","pick","pick"] [[[[1,1,5,5]]],[],[],[]]

Output

[2, 3, ] [4, 1, ] [3, 5, ]