यह जांचने के लिए प्रश्न कि क्या C++ प्रोग्राम में एक मंडली में बक्से में शामिल होना संभव है

इस समस्या में, हमें एक संख्या n दी गई है जो एक वृत्त के किनारे पर स्थित n बक्सों को दर्शाती है। और क्यू प्रश्न हैं जिनमें से प्रत्येक में दो पूर्णांक, ए और बी शामिल हैं। हमारा काम प्रश्नों को हल करने के लिए एक प्रोग्राम बनाना है ताकि यह जांचा जा सके कि क्या मंडलियों में बक्से में शामिल होना संभव है।

समस्या का विवरण - प्रत्येक प्रश्न को हल करने के लिए, हमें बॉक्स ए और बॉक्स बी को रॉड से जोड़ने की संभावना को इस तरह से जांचना होगा कि अंतिम क्वेरी से बॉक्स का प्रतिच्छेदन बाधित न हो। हमें संभव प्रिंट करना होगा या संभव नहीं शर्त के आधार पर।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

n = 6 Q = 3 Queries = {{1, 3}, {2, 5}, {4, 5}}

आउटपुट

Possible
Not possible
Possible

स्पष्टीकरण

ठोस रेखाएँ ऐसी छड़ें होती हैं जिन्हें जोड़ा जा सकता है, जबकि धराशायी रेखा वह रेखा होती है जिसे जोड़ा नहीं जा सकता।

समाधान दृष्टिकोण

समस्या का एक सरल समाधान यह है कि प्रत्येक प्रश्न के लिए क्वेरी का समाधान ढूंढ़कर, हम यह पता लगाएंगे कि क्या दिए गए बॉक्स बॉक्स ए और बॉक्स बी को जोड़ा जा सकता है। इसके लिए, हमें अंतिम क्वेरी के मानों को संदर्भ बिंदुओं के रूप में रखना होगा और फिर जांचना होगा कि कनेक्शन संभव है या नहीं।

आइए बॉक्सों पर विचार करें a और ख संदर्भ ref1 और ref2 के रूप में क्वेरी (i-1) का। फिर ज्ञात कीजिए कि क्या बिंदु a और b छड़ के विपरीत दिशा में हैं।

इसके लिए हम दो शर्तों की जांच करेंगे,

शर्त 1 - अगर (ref1

शर्त 2 - अगर (ref1

दोनों ही मामलों में, परिणाम संभव नहीं होगा।

#include <iostream>
using namespace std;
int printSolutoin(int n, int a, int b, int ref1, int ref2, int lastConn){
   if(lastConn == 0 && a != b)
      return 1;
      int temp;
   if(a > b){
      temp = a;
      a = b;
      b = temp;
   }
   if(ref1 > ref2){
      temp = ref1;
      ref1 = ref2;
      ref2 = temp;
   }
   if( ( ref1 < a && a < b && b < ref2) )
      return 1;
   if( (ref1 <= a <= ref2) && (ref2 <= b <= n) ) return 0;
   else if( (ref1 <= b <= ref2) && (ref2 <= a <= n) )
      return 0;
      return 0;
      return 1;
}
void solveAllQueries(int n, int q, int query[][2]){
   int lastConn = printSolutoin(n, query[0][0], query[0][1], 0, 0, 0);
   lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
   for(int i = 1; i < q; i++){
      lastConn = printSolutoin(n, query[i][0], query[i][1], query[i - 1][0], query[0][1],       lastConn);
      lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
   }
}
int main() {
   int n = 6;
   int Q = 3;
   int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
   return 0;
}

Possible
Not Possible
Possible