C++プログラムでサークル内のボックスを結合できるかどうかを確認するためのクエリ

この問題では、円の端にあるn個のボックスを表す番号nが与えられます。そして、それぞれが2つの整数aとbで構成されるQクエリがあります。私たちの仕事は、クエリを解決して、ボックスを円で結合できるかどうかを確認するプログラムを作成することです。

問題の説明 −各クエリを解決するには、最後のクエリのボックスの交差が妨げられないように、ボックスaとボックスbをロッドで接続する可能性を確認する必要があります。 可能を印刷する必要があります または不可能 状態に基づいています。

問題を理解するために例を見てみましょう

入力

n = 6 Q = 3 Queries = {{1, 3}, {2, 5}, {4, 5}}

出力

Possible
Not possible
Possible

説明

実線は接続可能な棒であり、破線は接続できない線です。

ソリューションアプローチ

この問題の簡単な解決策は、各クエリのクエリの解決策を見つけることです。指定されたボックスボックスaとボックスbを接続できるかどうかを調べます。このためには、最後のクエリの値を参照ポイントとして保持してから、接続が可能かどうかを確認する必要があります。

ボックスについて考えてみましょうa およびb 参照ref1およびref2としてのクエリ（i-1）の。次に、点aとbがロッドの反対側にあるかどうかを確認します。

このために、2つの条件を確認します

条件1 − if（ref1

条件2 − if（ref1

どちらの場合も、結果は得られません。

これが私たちのソリューションの働きを説明するためのプログラムです

例

#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 <= ref2) && (ref2 <= b <= n) ) return 0;
   else if( (ref1 <= b <= ref2) && (ref2 <= 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<<"Possible\n":cout<<"Not Possible\n";
   for(int i = 1; i < q; i++){
      lastConn = printSolutoin(n, query[i][0], query[i][1], query[i - 1][0], query[0][1],       lastConn);
      lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
   }
}
int main() {
   int n = 6;
   int Q = 3;
   int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
   return 0;
}

出力

Possible
Not Possible
Possible