ตรวจสอบการเชื่อมกล่องเป็นวงกลมได้หรือไม่ใน C++

ภาพรวมปัญหา

มีกล่องเรียงเป็นวงกลม 1 ถึง n ตรวจสอบว่าเชื่อมกล่อง i กับ j ด้วยท่อนได้หรือไม่ โดยไม่ให้ท่อนตัดกัน

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

#include <bits/stdc++.h>
using namespace std;

void isPossible(int n, int q, int queryi[], int queryj[]) {
    int arr[50] = {0};
    for (int k = 0; k < q; k++) {
        int check = 0;
        if (queryj[k] < queryi[k]) swap(queryi[k], queryj[k]);
        
        if (arr[queryi[k]] != 0 || arr[queryj[k]] != 0) check = 1;
        else if (queryi[k] == queryj[k]) check = 1;
        else {
            for (int i = 1; i < queryi[k]; i++)
                if (arr[i] != 0 && arr[i] < queryj[k] && queryi[k] < arr[i]) {
                    check = 1; break;
                }
            if (check == 0) {
                for (int i = queryi[k]+1; i < queryj[k]; i++)
                    if (arr[i] != 0 && arr[i] > queryj[k]) {
                        check = 1; break;
                    }
            }
        }
        
        if (check == 0) {
            cout << "Possible" << endl;
            arr[queryi[k]] = queryj[k];
            arr[queryj[k]] = queryi[k];
        } else cout << "Not Possible" << endl;
    }
}

int main() {
    int size = 5, q = 2;
    int queryi[] = {3, 5};
    int queryj[] = {1, 4};
    isPossible(size, q, queryi, queryj);
    return 0;
}

ผลลัพธ์

Possible
Possible