C++에서 겹치지 않는 직사각형의 임의의 점

겹치지 않는 축으로 정렬된 직사각형의 목록이 있다고 가정하고 직사각형으로 덮인 공간의 점인 정수를 무작위로 균일하게 선택하는 함수 선택을 작성해야 합니다. 따라서 몇 가지 사항을 염두에 두어야 합니다 -

• 정수 점은 정수 좌표를 갖는 점입니다.
• 사각형 둘레의 점은 직사각형으로 덮인 공간에 포함됩니다.
• 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()을 세 번 호출하면 출력은 [4,1], [4,1], [3,3]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 두 개의 배열 영역을 만들고 사각형
• 이니셜라이저에서 다음을 수행하십시오 -
• rect :=rect, 합계 :=0
• 0에서 rect의 크기까지 범위에 있는 i의 경우 – 1
  • (x1, y1) :=(직사각형[i, 0], 직사각형[i, 1])
  • (x2, y2) :=(직사각형[i, 2], 직사각형[i, 3])
  • 온도 :=|x2 – x1 + 1| * |y2 – y1 + 1|
  • sum :=sum + temp, 합계를 영역에 삽입
• 선택 방법에서 다음을 수행합니다. -
• randArea :=난수 모드 합 + 1
• 범위 0에서 영역 크기 – 1에 있는 i의 경우
  • randArea <=area[i]이면 루프에서 나옵니다.
• dist_x :=난수 모드 |rect[i,0] – rect[i,2] + 1|
• dist_y :=난수 모드 |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, ]