C++でページを指定した角度で回転できるかどうかを判定する方法

この問題では、ページ上にある3つの点 x、y、z の座標が与えられます。私たちのタスクは、ページをある角度で回転させることが可能かどうかを判定することです。

ここでの回転とは、「x」の新しい位置が元の「y」の位置に移り、「y」の新しい位置が元の「z」の位置に移るような回転を指します。そして、回転の可否に応じて「Yes」または「No」を出力します。

問題を理解するための具体例

入力：x = (0, 1), y = (1, 0), z = (0, -1)

出力：Yes

説明：

この場合、ページを90度回転させることで、条件を満たす配置を実現できます。

解法のアプローチ

ページをある角度で回転できるかどうかは、次の条件によって判定できます。

• 点xと点yの距離が点yと点zの距離と等しいこと。
• さらに、3つの点すべてが同一直線上に乗っている場合は回転が不可能です。距離が等しい場合に3点が同一直線上にあるのは、yがxzの中点になるときだけなので、このケースを除外すればよいことになります。

つまり、「xy間の距離＝yz間の距離」かつ「yがxzの中点ではない」という2つの条件を満たせば、回転は可能だと判断できます。

解法の動作を示すプログラム

コード例

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

int possibleOrNot(int coordinates[3][2]){
   
   long long dis1 = pow(coordinates[1][0] - coordinates[0][0], 2) + pow(coordinates[1][1] - coordinates[0][1], 2);
   long long dis2 = pow(coordinates[2][0] - coordinates[1][0], 2) + pow(coordinates[2][1] - coordinates[1][1], 2);

   if(dis1 != dis2)
      return 0;
   else if (coordinates[1][0] == ((coordinates[0][0] + coordinates[2][0]) / 2.0) &amp;&amp; coordinates[1][1] == ((coordinates[0][1] + coordinates[2][1]) / 2.0))
      return 0;
   else
      return 1;
}

int main() {
   
   int coordinates[3][2] = {{0 , 1}, {1 , 0}, {0, -1} } ;
   if ( possibleOrNot(coordinates))
      cout<<"The rotation of page is possible";
   else
      cout<<"The rotation of page is not possible";
   
   return 0;
}

コードの解説

関数 possibleOrNot() の処理の流れは以下の通りです。

1. まず、点xと点yの距離の2乗（dis1）と、点yと点zの距離の2乗（dis2）を計算します。平方根を取らずに2乗のまま比較することで、誤差を避けられます。
2. dis1 と dis2 が異なる場合は、回転不可能として 0 を返します。
3. 次に、y の座標が x と z の中点と一致するかどうかを確認します。一致する場合は3点が同一直線上にあるため、回転不可能として 0 を返します。
4. どちらの条件にも該当しなければ、回転可能として 1 を返します。

出力

The rotation of page is possible

このように、与えられた座標に対して距離の一致と同一直線上にないことの2点をチェックするだけで、ページの回転可否を効率的に判定できます。計算量は O(1) と非常にシンプルなアルゴリズムです。