C++ এ নন-ওভারল্যাপিং আয়তক্ষেত্রে র্যান্ডম পয়েন্ট

ধরুন আমাদের কাছে নন-ওভারল্যাপিং অক্ষ-সারিবদ্ধ আয়তক্ষেত্রগুলির একটি তালিকা রয়েছে, আমাদের একটি ফাংশন পিক লিখতে হবে যা এলোমেলোভাবে এবং অভিন্নভাবে একটি পূর্ণসংখ্যা বাছাই করে, আয়তক্ষেত্র দ্বারা আচ্ছাদিত স্থানটিতে বিন্দু। তাই আমাদের কিছু পয়েন্ট মনে রাখতে হবে -

• একটি পূর্ণসংখ্যা বিন্দু এমন একটি বিন্দু যার পূর্ণসংখ্যা স্থানাঙ্ক রয়েছে।
• একটি আয়তক্ষেত্রের পরিধির একটি বিন্দু আয়তক্ষেত্র দ্বারা আচ্ছাদিত স্থানের অন্তর্ভুক্ত।
• ith আয়তক্ষেত্র =rects[i] বোঝায় [x1,y1,x2,y2], যেখানে [x1, y1] হল নীচের-বাম কোণের পূর্ণসংখ্যা স্থানাঙ্ক এবং [x2, y2] হল এর পূর্ণসংখ্যা স্থানাঙ্ক উপরের-ডান কোণে।
• প্রতিটি আয়তক্ষেত্রের দৈর্ঘ্য এবং প্রস্থ 2000 এর বেশি নয়৷
• 1 <=rects.length <=100
• পূর্ণসংখ্যা স্থানাঙ্কের একটি অ্যারে হিসাবে একটি বিন্দু ফেরত নিন [p_x, p_y]

ইনপুট যদি [1,1,5,5] এর মত হয় এবং আমরা পিক() কে তিনবার কল করি, তাহলে আউটপুট হবে [4,1], [4,1], [3,3]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• দুটি অ্যারে এরিয়া তৈরি করুন এবং রেক্ট করুন
• ইনিশিয়েলাইজারে নিম্নলিখিতগুলি করুন -
• rect :=rects, sum :=0
• আমি রেঞ্জ 0 থেকে রেক্টের আকার - 1
  • (x1, y1) :=(rects[i, 0], rects[i, 1])
  • (x2, y2) :=(rects[i, 2], rects[i, 3])
  • তাপ :=|x2 – x1 + 1| * |y2 – y1 + 1|
  • সমষ্টি :=সমষ্টি + তাপমাত্রা, এবং ক্ষেত্রফল যোগ করুন
• পিক পদ্ধতিতে, নিম্নলিখিতগুলি করুন -
• randArea :=র্যান্ডম সংখ্যা মোড যোগফল + 1
• আমি 0 থেকে ক্ষেত্রফলের পরিসরে - 1
  • যদি 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 নেমস্পেস ব্যবহার করে std;void print_vector(vector v){ cout <<"["; for(int i =0; i এলাকা; ভেক্টর <ভেক্টর > রেক্ট; int যোগফল; সমাধান(ভেক্টর<ভেক্টর>&rects) { rect =rects; যোগফল =0; জন্য(int i =0; i  pick() { int randArea =rand() % sum + 1; int i; for(i =0; i > v ={{1, 1, 5, 5}}; সমাধান ob(v); print_vector(ob.pick()); print_vector(ob.pick()); print_vector(ob.pick());}

ইনপুট

["সমাধান", "পিক", "পিক", "পিক"][[[[1, 1, 5, 5]]], [], [], []]

আউটপুট