ধরুন আমাদের অвідলাপ না করা অ্যাক্সিস-অ্যালাইনড রেক্ট্যাঙ্গেলের একটি তালিকা 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 := 0
- i = 0 থেকে rects-এর আকার – ১ পর্যন্ত
- (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 + 1
- i = 0 থেকে area-এর আকার – ১ পর্যন্ত
- যদি 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, ]
