C++で同一直線上に存在する最大点数を求めるアルゴリズム

問題概要

2次元平面上に複数の点が与えられたとき、同じ直線上に存在する点の最大数を求めるのがこの問題の目的です。

例えば、下図のような6つの点が与えられた場合、最も多くの点が乗っている直線上には4つの点が存在します。

解法のアプローチ

この問題は、隣り合う2点を通る直線を基準にして、残りのすべての点がその直線上に乗っているかどうかを順番に判定していくことで解けます。

3点 (x1, y1)、(x2, y2)、(x3, y3) が同一直線上にあるかどうかは、「傾きが等しい」こと、すなわち外積(クロス積)が0になることを利用して判定できます。

(y3 − y2) × (x2 − x1) = (y2 − y1) × (x3 − x2)

この式が成り立てば3点は同一直線上にあるとみなせます。割り算を使わず掛け算だけで判定するため、浮動小数点誤差やゼロ除算の問題を回避できるのがポイントです。

具体的な手順は以下の通りです。

• n を点の総数とし、n < 3 であればそのまま n を返す(3点未満なら全点が必ず1本の直線上に載るため)
• ans を 2 で初期化する(任意の2点は必ず1本の直線を定義できるため)
• i を 1 から n−1 まで繰り返す:
  • count を 0 に初期化する
  • インデックス i−1 と i の2点をそれぞれ p1、p2 として取り出す
  • p1 と p2 が同一の点である場合:
    • j を 0 から n−1 まで繰り返し、points[j] の座標が p1 と完全に一致していれば count をインクリメントする
  • それ以外の場合:
    • j を 0 から n−1 まで繰り返し、各点 p3 に対して上記の共線判定式を満たしていれば count をインクリメントする
  • ans を max(ans, count) で更新する
• 最後に ans を返す

C++実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if(n<3)return n;
        int ans = 2;
        for(int i = 1;i<n;i++){
            int count = 0;
            lli x1 = points[i-1][0];
            lli x2 = points[i][0];
            lli y1 = points[i-1][1];
            lli y2 = points[i][1];
            if(x1 == x2 && y1 == y2){
                for(int j =0;j<n;j++){
                    if(points[j][0] ==x1 && points[j][1] == y1)count++;
                }
            } else {
                for(int j =0;j<n;j++){
                    int x3 = points[j][0];
                    int y3 = points[j][1];
                    if((y3-y2)*(x2-x1) == (y2-y1)*(x3-x2))count++ ;
                }
            }
            ans = max(ans, count);
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
    cout << (ob.maxPoints(v));
}

入力例

[{1,1},{3,2},{5,3},{4,1},{2,3},{1,5}]

出力例

4

まとめ

このアルゴリズムは、基準となる2点の組み合わせを n−1 通り変えながら全点との共線性を調べるため、時間計算量は O(n²) となります。また、座標値同士の掛け算でオーバーフローが発生しないよう、long long 型を使用している点にも注目してください。傾きの比較を外積による掛け算のみで行うことで、精度を落とさずに正確な判定ができるのがこの手法の大きな利点です。