C++で2点間の格子点(整数座標の点)の数を求める方法

はじめに

このチュートリアルでは、与えられた2つの点の間に存在する整数座標の点(格子点)の数を求めるプログラムをC++で作成します。

2点を結ぶ線分上の格子点の数は、次の式で求めることができます。

gcd(abs(x1 - x2), abs(y1 - y2)) - 1

ただし、線分が座標軸に平行な場合は特別な扱いが必要です。

• x軸に平行な場合(両点のy座標が等しい): 格子点の数は abs(x1 - x2) - 1
• y軸に平行な場合(両点のx座標が等しい): 格子点の数は abs(y1 - y2) - 1

つまり、両方の点のy座標が一致していれば線分はx軸に平行となり、x座標が一致していればy軸に平行となります。

入力例

pointOne = [1, 5]
pointTwo = [1, 3]

出力例

1

この例では、両点のx座標がどちらも1なので、線分はy軸に平行です。したがって、abs(5 - 3) - 1 = 1 という結果になります。

アルゴリズム

• 2つの点を初期化します。
• 線分がx軸に平行かどうか(y座標が等しいか)を確認します。平行であれば abs(x1 - x2) - 1 を返します。
• 線分がy軸に平行かどうか(x座標が等しいか)を確認します。平行であれば abs(y1 - y2) - 1 を返します。
• どちらの軸にも平行でない場合は、gcd(abs(x1 - x2), abs(y1 - y2)) - 1 を計算します。
• 結果を出力します。

C++での実装

以下は、上記のアルゴリズムをC++で実装したコードです。

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

// ユークリッドの互除法による最大公約数の計算
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int getCount(int pointOne[], int pointTwo[]) {
    // x座標が等しい場合(y軸に平行)
    if (pointOne[0] == pointTwo[0]) {
        return abs(pointOne[1] - pointTwo[1]) - 1;
    }
    // y座標が等しい場合(x軸に平行)
    if (pointOne[1] == pointTwo[1]) {
        return abs(pointOne[0] - pointTwo[0]) - 1;
    }
    // それ以外の場合
    return gcd(abs(pointOne[0] - pointTwo[0]), abs(pointOne[1] - pointTwo[1])) - 1;
}

int main() {
    int pointOne[] = {1, 3}, pointTwo[] = {10, 12};
    cout << getCount(pointOne, pointTwo) << endl;
    return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

8

この例では、gcd(abs(1 - 10), abs(3 - 12)) - 1 = gcd(9, 9) - 1 = 8 となるため、答えは8になります。