Điểm ngẫu nhiên trong hình chữ nhật không chồng chéo trong C ++

Giả sử chúng ta có một danh sách các hình chữ nhật được căn chỉnh theo trục không trùng nhau, chúng ta phải viết một hàm chọn ngẫu nhiên và thống nhất chọn một số nguyên, điểm trong không gian được bao phủ bởi các hình chữ nhật. Vì vậy, chúng ta phải ghi nhớ một số điểm -

• Một điểm nguyên là một điểm có tọa độ nguyên.
• Một điểm trên chu vi của hình chữ nhật được bao gồm trong không gian được bao phủ bởi các hình chữ nhật.
• Hình chữ nhật thứ i =rects [i] biểu thị [x1, y1, x2, y2], trong đó [x1, y1] là tọa độ nguyên của góc dưới cùng bên trái và [x2, y2] là tọa độ nguyên của góc trên bên phải.
• Chiều dài và chiều rộng của mỗi hình chữ nhật không vượt quá 2000.
• 1 <=rects.length <=100
• chọn trả về một điểm dưới dạng một mảng tọa độ số nguyên [p_x, p_y]

Nếu đầu vào là [1,1,5,5] và chúng ta gọi pick () ba lần, thì đầu ra sẽ là [4,1], [4,1], [3,3]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo hai mảng vùng và trực tràng
• Trong trình khởi tạo, hãy làm như sau -
• direct:=rects, sum:=0
• cho tôi trong phạm vi từ 0 đến kích thước của rects - 1
  • (x1, y1):=(rects [i, 0], rects [i, 1])
  • (x2, y2):=(rects [i, 2], rects [i, 3])
  • tạm thời:=| x2 - x1 + 1 | * | y2 - y1 + 1 |
  • sum:=sum + temp và chèn tổng vào vùng
• Trong phương pháp chọn, hãy thực hiện như sau -
• randArea:=số ngẫu nhiên mod sum + 1
• cho tôi trong phạm vi từ 0 đến kích thước của vùng - 1
  • nếu randArea <=area [i], thì thoát khỏi vòng lặp
• dist_x:=ngẫu nhiên mod số | trực tràng [i, 0] - trực tràng [i, 2] + 1 |
• dist_y:=ngẫu nhiên mod số | trực tràng [i, 1] - trực tràng [i, 3] + 1 |
• trả về một cặp (dist_x + direct [i, 0], dist_y + direct [i, 1])

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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];
         int y1 = rects[i][1];
         int x2 = rects[i][2];
         int 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;
      for(i = 0; 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]};
   }
};
main(){
   vector<vector<int> > v = {{1, 1, 5, 5}};
   Solution ob(v);
   print_vector(ob.pick());
   print_vector(ob.pick());
   print_vector(ob.pick());
}

Đầu vào

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

Đầu ra

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