সি++-এ বৃত্তাকার বাক্স সংযোগ সম্ভবতা যাচাই করার কোয়েরি সমাধান

সমস্যা বিবরণ

n সংখ্যক বাক্স বৃত্তের পরিধিতে আছে। Qটি কোয়েরি দেওয়া আছে, প্রতিটিতে দুটি ইন্টিজার a, b। চেক করতে হবে a এবং b বাক্সকে একটি রড দিয়ে সংযোগ করা সম্ভব কিনা, যাতে পূর্বের কোয়েরির সংযোগ বাধা না পায়।

উদাহরণ: n = 6, Q = 3, Queries = {{1,3}, {2,5}, {4,5}}

আউটপুট: Possible, Not possible, Possible

সমাধানের পদ্ধতি

1. প্রথম কোয়েরি সবসময় Possible।
2. পূর্বের কোয়েরির দুটি বাক্সকে রেফারেন্স পয়েন্ট (ref1, ref2) ধরুন।
3. নতুন কোয়েরির a, b যদি রেফারেন্স রডের বিপরীত পাশে পড়ে (ক্রস করে), তবে Not possible।
4. শর্ত:
   • ref1 < a < ref2 && ref2 < b < n
   • ref1 < b < ref2 && ref2 < a < n
5. অন্যথায় Possible।

উদাহরণ কোড

#include <iostream>
using namespace std;

int printSolution(int n, int a, int b, int ref1, int ref2, int lastConn) {
    if (lastConn == 0 && a != b) return 1;
    if (a > b) swap(a, b);
    if (ref1 > ref2) swap(ref1, ref2);
    if (ref1 < a && a < b && b < ref2) return 1;
    if (ref1 <= a && a <= ref2 && ref2 <= b && b <= n) return 0;
    if (ref1 <= b && b <= ref2 && ref2 <= a && a <= n) return 0;
    return 1;
}

void solveAllQueries(int n, int q, int query[][2]) {
    int lastConn = printSolution(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 = printSolution(n, query[i][0], query[i][1], query[i-1][0], query[i-1][1], lastConn);
        lastConn ? cout << "Possible\n" : cout << "Not Possible\n";
    }
}

int main() {
    int n = 6, Q = 3;
    int query[Q][2] = {{1,3}, {2,5}, {4,5}};
    solveAllQueries(n, Q, query);
    return 0;
}

আউটপুট

Possible
Not Possible
Possible