C++でボックスを円状に結合できるかを確認するクエリの判定方法

このチュートリアルでは、ボックスを円状に結合できるかどうかを確認するクエリを処理するプログラムについて解説します。

ここでは、1からnまでの番号が振られたボックスが円状に並んでいるものとします。各クエリに対して、ボックスiとボックスjを棒で接続しても、すでに設置済みの棒と交差しないかどうかを判定するのが課題です。

アルゴリズムの考え方

各クエリを処理する際は、まずiとjの大小関係を整えます。新しい棒が既存の棒と交差するのは、一方の棒の両端がもう一方の棒の両端の間に挟まれる場合です。そこで、すでに接続済みのボックスの位置情報を配列に記録しておき、交差の条件に該当するかどうかを順にチェックします。交差しないと判定できれば「Possible」を出力して接続情報を記録し、交差する場合は「Not Possible」を出力します。

実装例

#include <bits/stdc++.h>
using namespace std;
//ボックスで円を作ることが可能かどうかを確認する
void isPossible(int n, int q, int queryi[], int queryj[]) {
   int arr[50];
   for (int i = 0; i <= n; i++)
      arr[i] = 0;
   for (int k = 0; k < q; k++) {
      int check = 0;
      if (queryj[k] < queryi[k]) {
         int temp = queryi[k];
         queryi[k] = queryj[k];
         queryj[k] = temp;
      }
      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;
   int q = 2;
   int queryi[] = { 3, 5 };
   int queryj[] = { 1, 4 };
   isPossible(size, q, queryi, queryj);
   return 0;
}

出力

Possible
Possible

この例では、ボックス3と1、ボックス5と4をそれぞれ棒で接続しても既存の棒と交差しないため、両方のクエリに対して「Possible」が出力されます。