すべての座標点が2本の平行線上に収まるかどうかを判定するC++プログラム

この記事では、与えられたすべての座標点が2本の平行線だけに収まるかどうかを判定するプログラムについて解説します。

問題の概要

判定の対象となるのは、座標が (i, arr[i]) となるような配列です。例として、次の配列を考えてみましょう。

arr = {2,6,8,12,14}

この場合、これらの点は2本の平行線上に配置できます。1本目の直線には (1,2)、(3,8)、(5,14) が含まれ、2本目の直線には残りの座標、つまり (2,6) と (4,12) が含まれます。

解法のアプローチ

この問題は、与えられた点が作る直線の傾きを比較することで解くことができます。ご存知のとおり、点 (a1, b1) と点 (a2, b2) を通る直線の傾きは次の式で表されます。

傾き = (b2 - b1) / (a2 - a1)

同じ考え方で、配列から3つの点を取り出して傾きを比較できます。直線は2本しかないため、3つの点のうち少なくとも2つは必ず同じ直線上に存在することになります。

そこで、3つの点を取り出し、それらを通る直線の切片を計算します。切片がちょうど2つの異なる値になれば、配列内のすべての点は2本の平行線上に表現できることになります。そうでなければ、表現できません。

プログラムは、条件が満たされる場合は 1 を、満たされない場合は 0 を返します。

実装例

#include <bits/stdc++.h>
using namespace std;
// 切片がちょうど2つの値になるかどうかを計算する
bool is_intercept(double slope, int arr[], int num) {
    set<double> Lines;
    for (int i = 0; i < num; i++)
        Lines.insert(arr[i] - slope * (i));
    return Lines.size() == 2;
}
// 与えられた点の傾きを調べる
bool is_parallel(int arr[], int num) {
    bool slope1 = is_intercept(arr[1] - arr[0], arr, num);
    bool slope2 = is_intercept(arr[2] - arr[1], arr, num);
    bool slope3 = is_intercept((arr[2] - arr[0]) / 2, arr, num);
    return (slope1 || slope2 || slope3);
}
int main() {
    int arr[] = {2,6,8,12,14};
    int num = sizeof(arr)/sizeof(arr[0]);
    cout << (int)is_parallel(arr, num);
    return 0;
}

出力

1

コードの解説

is_intercept関数は、与えられた傾きをもとに、各点における切片の値 arr[i] - slope * i を計算し、set に格納します。set は重複する値を保持しないため、最終的な要素数が2であれば、すべての点が2本の平行線上に存在することを意味します。

is_parallel関数は、最初の3点から導ける3通りの傾き（arr[1]-arr[0]、arr[2]-arr[1]、(arr[2]-arr[0])/2）をそれぞれ試します。3点のうち2点は必ず同じ直線上にあるため、正しい傾きは必ずこの中に含まれます。いずれか1つでも条件を満たせば true を返します。

このアルゴリズムの計算量は O(N) であり、点の数が増えても効率的に判定できます。