C++の重複しない長方形のランダムポイント

重なり合わない軸に位置合わせされた長方形の長方形のリストがあるとすると、長方形で覆われた空間内の整数をランダムかつ均一に選択する関数pickを作成する必要があります。したがって、いくつかの点に留意する必要があります-

• 整数点は、整数座標を持つ点です。
• 長方形の周囲の点は、長方形で覆われたスペースに含まれます。
• i番目の長方形=rects[i]は[x1、y1、x2、y2]を示します。ここで、[x1、y1]は左下隅の整数座標であり、[x2、y2]は右上隅。
• 各長方形の長さと幅は2000を超えません。
• 1 <=rects.length <=100
• 整数座標の配列としてポイントを返すを選択します[p_x、p_y]

入力が[1,1,5,5]のようで、pick（）を3回呼び出すと、出力は[4,1]、[4,1]、[3,3]

これを解決するには、次の手順に従います-

• 2つの配列領域を作成して長方形にします
• イニシャライザで次の手順を実行します-
• rect：=rects、sum：=0
• 0からrectsのサイズまでの範囲のiの場合– 1
  • （x1、y1）：=（rects [i、0]、rects [i、1]）
  • （x2、y2）：=（rects [i、2]、rects [i、3]）
  • temp：=| x2 – x1 + 1 | * | y2 – y1 + 1 |
  • sum：=sum + temp、およびsumを領域に挿入
• pickメソッドで、次のようにします-
• randArea：=乱数mod sum + 1
• 範囲0から領域のサイズまでのiの場合– 1
  • randArea <=area [i]の場合、ループから抜け出します
• dist_x：=乱数mod | rect [i、0] – rect [i、2] + 1 |
• dist_y：=乱数mod | rect [i、1] – rect [i、3] + 1 |
• ペアを返す（dist_x + rect [i、0]、dist_y + rect [i、1]）

理解を深めるために、次の実装を見てみましょう-

例

#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());
}

入力

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

出力

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