C++で直線の方程式を満たす順序付き点ペアの数を求める方法

問題の概要

本記事では、直線の方程式 y = mx + c を満たす順序付き点ペアの数を求める問題を解説します。配列と、傾き m、切片 c が与えられたとき、配列の要素から選んだ順序付きペア（i, j）のうち、arr[j] = m × arr[i] + c を満たすものの個数を数えます。まずは具体例を見てみましょう。

入力例

arr = [1, 2, 3]
m = 1
c = 1

出力例

2

この例では、直線 y = x + 1 上に乗る点のペアとして (1, 2) と (2, 3) の2組が該当します。

アルゴリズム

考え方はシンプルで、取り得るすべてのペアを総当たり（ブルートフォース）で調べる方法です。手順は以下の通りです。

• 配列、m、c を初期化します。
• 二重ループを使って、配列から作れるすべての順序付きペア（i, j）を列挙します。
  • 各ペアについて、直線の方程式を満たすかどうかを判定します。
  • 判定は、値を方程式に代入して arr[j] == m * arr[i] + c が成り立つかを確認するだけです。
  • 方程式を満たすペアであれば、カウントを1増やします。
• 最終的なカウントを結果として返します。

すべてのペアを調べるため、計算量は O(n²) となります。

C++での実装

上記のアルゴリズムをC++で実装したコードが次の通りです。

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

bool isSatisfyingLineEquation(int arr[], int i, int j, int m, int c) {
    if (i == j) {
        return false;
    }
    return arr[j] == m * arr[i] + c;
}

int getOrderedPointsPairCount(int arr[], int n, int m, int c) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (isSatisfyingLineEquation(arr, i, j, m, c)) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n = 10;
    int m = 1, c = 1;
    cout << getOrderedPointsPairCount(arr, n, m, c) << endl;
    return 0;
}

実行結果

このコードを実行すると、次の出力が得られます。

9

配列が 1 から 10 までの連続する整数の場合、y = x + 1 を満たすペアは (1, 2)、(2, 3)、…、(9, 10) の9組になるため、正しく 9 が出力されます。