C ++中非重叠矩形中的随机点

假设我们有一个不重叠的，与轴对齐的矩形rects的列表，我们必须编写一个函数pick，它随机且均匀地选取一个整数，指向矩形所覆盖的空间。所以我们必须记住一些要点-

• 整数点是具有整数坐标的点。

• 矩形周长上的点包含在矩形所覆盖的空间中。

• 第ith个矩形= rects [i]表示[x1，y1，x2，y2]，其中[x1，y1]是左下角的整数坐标，而[x2，y2]是左上角的整数坐标。右上角。

• 每个矩形的长度和宽度不超过2000。

• 1 <=矩形长度<= 100

• 选择将点作为整数坐标[p_x，p_y]的数组返回

如果输入类似于[1,1,5,5]，我们调用pick()了三次，那么输出将为[4,1]，[4,1]，[3,3]

为了解决这个问题，我们将遵循以下步骤-

• 使两个数组区域和矩形

• 在初始化程序中执行以下操作-

• 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：=随机数模和+ 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, ]