मान लीजिए हमारे पास गैर-ओवरलैपिंग अक्ष-संरेखित आयतों की एक सूची rects है, हमें एक फ़ंक्शन pick लिखना है जो आयतों द्वारा कवर किए गए स्थान में एक पूर्णांक बिंदु को यादृच्छिक और समान रूप से चुनता है। इसलिए हमें कुछ बिंदुओं को ध्यान में रखना होगा:
- एक पूर्णांक बिंदु वह बिंदु है जिसके पूर्णांक निर्देशांक हैं।
- आयत की परिधि पर एक बिंदु आयतों द्वारा कवर किए गए स्थान में शामिल है।
- i-वां आयत = rects[i] [x1,y1,x2,y2] को दर्शाता है, जहां [x1, y1] निचले-बाएं कोने के पूर्णांक निर्देशांक हैं, और [x2, y2] ऊपरी-दाएं कोने के पूर्णांक निर्देशांक हैं।
- प्रत्येक आयत की लंबाई और चौड़ाई 2000 से अधिक नहीं है।
- 1 <= rects.length <= 100
- pick एक बिंदु को पूर्णांक निर्देशांकों की सरणी [p_x, p_y] के रूप में लौटाता है
यदि इनपुट [1,1,5,5] है, और हम pick() को तीन बार कॉल करते हैं, तो आउटपुट [4,1], [4,1], [3,3] होगा
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- दो सरणियां
areaऔरrectबनाएं - आरंभकर्ता में निम्नलिखित करें:
rect := rects, sum := 0i = 0 से rects का आकार - 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 को area में डालें
- pick विधि में, निम्नलिखित करें:
randArea := यादृच्छिक संख्या mod sum + 1i = 0 से area का आकार - 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]};
}
};
int 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, ]