C++プログラムで円周上のボックスを接続できるか判定するクエリ問題

この問題では、円周上に配置された n 個のボックスが与えられます。さらに、2つの整数 a と b のペアからなる Q 個のクエリが与えられ、各クエリについてボックス同士を接続できるかどうかを判定するプログラムを作成します。

問題の概要

各クエリを処理する際には、直前のクエリで引いた棒（ロッド）との交差を妨げないように、ボックス a と ボックス b を棒で結べるかどうかを確認する必要があります。判定結果に応じて「Possible（可能）」または「Not Possible（不可能）」を出力します。

入出力例で理解しよう

入力

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

出力

Possible
Not possible
Possible

説明

下図において、実線は接続できる棒を表し、破線は接続できない棒を表しています。

解法アプローチ

最もシンプルな解決策は、各クエリごとに判定を行うことです。具体的には、与えられたボックス a と b が接続可能かどうかを、直前のクエリの値を基準点として保持しながらチェックしていきます。

ここで、クエリ (i-1) のボックス a と b をそれぞれ基準値 ref1、ref2 とみなします。そして、現在のクエリの点 a と b が、すでに引かれた棒を挟んで反対側に位置していないかを調べます。

この判定には、次の2つの条件を用います。

• 条件1： ref1 < a < ref2 かつ ref2 < b < n の場合
• 条件2： ref1 < b < ref2 かつ ref2 < a < n の場合

どちらかの条件に当てはまる場合、棒同士が交差してしまうため、結果は「Not Possible（不可能）」となります。

C++での実装例

以下は、この解法の動作を示すプログラムです。

#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