समस्या विवरण
इस समस्या में, हमें एक संख्या n दी गई है जो n बॉक्स को दर्शाती है जो एक सर्कल के किनारे पर स्थित हैं। और Q क्वेरीज हैं जिनमें प्रत्येक में दो पूर्णांक a और b होते हैं। हमारा कार्य सर्कल में बॉक्स जोड़ने की संभावना जांचने के लिए क्वेरीज को हल करने का प्रोग्राम बनाना है।
समस्या विवरण - प्रत्येक क्वेरी को हल करने के लिए, हमें बॉक्स a और बॉक्स b को एक रॉड से जोड़ने की संभावना जांचनी होगी ताकि पिछली क्वेरी के बॉक्स का इंटरसेक्शन डिस्टर्ब न हो। हमें शर्त के आधार पर संभव या संभव नहीं प्रिंट करना होगा।
उदाहरण
n = 6
Q = 3
Queries = {{1, 3}, {2, 5}, {4, 5}}
आउटपुट
संभव नहीं संभव
व्याख्या

ठोस रेखाएं वे रॉड हैं जिन्हें जोड़ा जा सकता है, जबकि बिंदीदार रेखा वह रेखा है जिसे नहीं जोड़ा जा सकता।
हल करने का दृष्टिकोण
समस्या का एक सरल हल प्रत्येक क्वेरी के लिए हल ढूंढना है। प्रत्येक क्वेरी के लिए, हम जांचेंगे कि दिए गए बॉक्स a और b को जोड़ा जा सकता है या नहीं। इसके लिए, हमें पिछली क्वेरी के मानों को रेफरेंस पॉइंट्स के रूप में रखना होगा और फिर जांचना होगा कि कनेक्शन संभव है या नहीं।
पिछली क्वेरी (i-1) के बॉक्स a और b को रेफरेंस ref1 और ref2 मानें। फिर ढूंढें कि पॉइंट्स a और b रॉड के विपरीत किनारों पर हैं या नहीं।
इसके लिए, हम दो शर्तों की जांच करेंगे:
शर्त 1 - यदि (ref1 < a < ref2 और ref2 < b < n)
शर्त 2 - यदि (ref1 < b < ref2 और ref2 < a < n)
दोनों मामलों में, परिणाम "संभव नहीं" होगा।
उदाहरण
#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 && a <= ref2) && (ref2 <= b && b <= n))
return 0;
else if ((ref1 <= b && b <= ref2) && (ref2 <= a && 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 << "संभव\n" : cout << "संभव नहीं\n";
for (int i = 1; i < q; i++) {
lastConn = printSolutoin(n, query[i][0], query[i][1], query[i-1][0], query[i-1][1], lastConn);
lastConn ? cout << "संभव\n" : cout << "संभव नहीं\n";
}
}
int main() {
int n = 6;
int Q = 3;
int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
solveAllQueries(n, Q, query);
return 0;
}
आउटपुट
संभव संभव नहीं संभव