Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में गैर-ओवरलैपिंग आयतों में यादृच्छिक बिंदु


मान लीजिए हमारे पास गैर-ओवरलैपिंग अक्ष-संरेखित आयतों की एक सूची 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 का आकार - 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 + 1
    • i = 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, ]

  1. C++ में कंप्यूटर ग्राफिक्स में पॉइंट क्लिपिंग एल्गोरिदम C++ में कंप्यूटर ग्राफिक्स में पॉइंट क्लिपिंग एल्गोरिदम

    कंप्यूटर ग्राफिक्स कंप्यूटर स्क्रीन पर छवियों और ग्राफिक्स को बनाने से संबंधित है। यहां, हम स्क्रीन को 2-D निर्देशांक प्रणाली के रूप में मानते हैं। यह निर्देशांक प्रणाली शीर्ष-बाएं (0,0) से शुरू होती है और नीचे-दाएं पर समाप्त होती है। व्यूइंग प्लेन कंप्यूटर ग्राफिक्स में ग्राफिक्स बनाने के लिए परिभ

  1. - C++ में जांचें कि कोई बिंदु वृत्त के अंदर है या नहीं

    मान लीजिए एक वृत्त दिया गया है (केंद्र के निर्देशांक और त्रिज्या), और एक अन्य बिंदु भी दिया गया है। हमें यह पता लगाना है कि बिंदु वृत्त के अंदर है या नहीं। इसे हल करने के लिए, हमें दिए गए बिंदु की वृत्त के केंद्र से दूरी निकालनी होगी। यदि वह दूरी त्रिज्या से कम या बराबर है, तो बिंदु वृत्त के अंदर है

  1. - C++ में static_cast

    static_cast का उपयोग सामान्य/साधारण प्रकार रूपांतरण के लिए किया जाता है। यह निहित प्रकार जबरदस्ती (implicit type coercion) के लिए भी जिम्मेदार कास्ट है और इसे स्पष्ट रूप से भी बुलाया जा सकता है। आपको इसका उपयोग फ्लोट को इंट में, चार को इंट में आदि जैसे मामलों में करना चाहिए। यह संबंधित प्रकार के क्