C++で点列が直線上にあるかどうかを判定する方法

(x, y) 座標からなるデータ点のリストが与えられたとき、それらの点が一直線上に並んでいるかどうかを判定します。たとえば、点が [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7)] のように並んでいる場合、これらの点は直線を形成しています。

解決のアプローチ

この問題は、隣接する2点間の差分から傾き(勾配)を求め、すべての点対で傾きが一定であるかを確認することで解けます。具体的な手順は以下のとおりです。

1. 最初の2点の座標差 (dx, dy) を計算し、最大公約数 (GCD) で約分して基準となる方向ベクトルを作ります。
2. 残りの各隣接点ペアについても同様に差分を計算し、GCDで約分します。
3. すべての方向ベクトルが基準ベクトルと一致すれば true を返し、1つでも異なれば false を返します。

GCDで約分してから比較するのがポイントです。傾きを小数として直接計算すると丸め誤差が生じるほか、x座標がすべて同じ「縦の直線」では傾き自体が定義できなくなります。整数比のまま方向ベクトルを比較すれば、こうした問題を回避して正確に判定できます。

実装例

以下のC++コードで実際の動作を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int gcd(int a, int b){
        return !b?a:gcd(b,a%b);
    }
    bool checkStraightLine(vector<vector<int>>& c) {
        bool ans =true;
        bool samex = true;
        bool samey = true;
        int a = c[1][0]-c[0][0];
        int b = c[1][1]-c[0][1];
        int cc = gcd(a,b);
        a/=cc;
        b/=cc;
        for(int i =1;i<c.size();i++){
            int x = c[i][0]-c[i-1][0];
            int y = c[i][1]-c[i-1][1];
            int z = gcd(x,y);
            x/=z;
            y/=z;
            ans =ans &&(x == a )&& (y == b );
        }
        return ans;
    }
};
main(){
Solution ob;
vector<vector<int>> c = {{1,2},{2,3},{3,4},{4,5},{5,6},{6,7}};
cout << ob.checkStraightLine(c);
}

入力

[[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]

出力

1
(1 は true を表します)

計算量

• 時間計算量: O(n log M) — n は点の数、M は座標値の最大値(GCD計算のコスト)
• 空間計算量: O(1)