โปรแกรมตรวจสอบการเชื่อมกล่องบนวงกลมไม่ให้ทับซ้อนใน C++

มี n กล่องวางอยู่บนขอบวงกลม และ Q คำถาม แต่ละคำถามมี (a,b) ต้องการทราบว่าสามารถเชื่อมกล่อง a กับ b ด้วยไม้กั้นได้หรือไม่ โดยไม่ให้ทับกับการเชื่อมก่อนหน้า

ตัวอย่าง: n=6, Q=3, queries={{1,3},{2,5},{4,5}} ผลลัพธ์: Possible, Not possible, Possible

วิธีแก้ปัญหา

เก็บการเชื่อมล่าสุดเป็นอ้างอิง (ref1, ref2) การเชื่อมใหม่ (a,b) เป็นไปไม่ได้ก็ต่อเมื่อ a และ b อยู่คนละฝั่งของเส้นเชื่อมเก่า (cross)

เงื่อนไขทับซ้อน: - ref1 < a < ref2 และ ref2 < b < n - ref1 < b < ref2 และ ref2 < a < n

ตัวอย่างโค้ด C++

#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);
    cout << (lastConn ? "Possible" : "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);
        cout << (lastConn ? "Possible" : "Not Possible") << '\n';
    }
}

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

เอาต์พุต

Possible
Not Possible
Possible