C++で2点間の最短距離を求めるプログラム ― 平面走査による効率的な解法

問題の概要

[x, y] 形式のユークリッド座標を要素とするリストが与えられます。この中から任意の2点を選んだときの2乗距離 (x₁ - x₂)² + (y₁ - y₂)² の最小値を求めるのが本記事の目的です。

例として、入力が coordinates = {{1, 2}, {1, 4}, {3, 5}} の場合を考えてみましょう。各ペアの2乗距離は次のようになります。

• (1, 2) と (1, 4)：(1−1)² + (2−4)² = 4
• (1, 2) と (3, 5)：(1−3)² + (2−5)² = 13
• (1, 4) と (3, 5)：(1−3)² + (4−5)² = 5

したがって、この場合の出力は 4 となります。

解法のアプローチ（平面走査）

この問題は、平面走査（スイープライン）の考え方を用いることで効率的に解けます。点を x 座標順にソートして処理しながら、「現在の注目点から距離的に意味のある範囲内にある点だけ」を std::map で管理するのがポイントです。具体的な手順は以下の通りです。

1. y座標をキー、x座標を値とするマップ ytorightmostx を用意する。
2. 座標配列 coordinates をソートする。
3. 答えを格納する変数 ret を無限大で初期化する。
4. 各点 p に対して以下を繰り返す。
   • it := ytorightmostx.lower_bound(p[1] − √ret)。つまり、p の y 座標から現在の最小距離の平方根を引いた値以上のキーのうち、最初に現れるものを取得する。
   • it がマップの末尾でない限り、次の処理を繰り返す。
     • yd := it のキー（y座標） − p[1]
     • yd > 0 かつ yd × yd ≥ ret になった場合は、これ以上 y 方向へ調べても無意味なためループを抜ける。
     • nxt := it の次の要素へのイテレータ
     • ret := min(ret, dist(p[0], p[1], it の値, it のキー))
     • xd := it の値（x座標） − p[0]
     • xd × xd ≥ ret の場合、そのエントリは今後の計算に二度と使えないため ytorightmostx から削除する。
     • it := nxt として処理を続行する。
   • ytorightmostx[p[1]] := p[0] として、現在の点をマップに登録する。
5. 最終的な ret を返す。

ここで使用する距離計算関数 dist(xl, yl, xr, yr) は、xd := xl − xr、yd := yl − yr とおき、xd × xd + yd × yd を返すシンプルなものです。

この手法では各点の登録が1回、削除も高々1回しか発生しないため、全体の計算量は O(n log n) 程度に抑えられます。全ペアを総当たりで調べる O(n²) の素朴な方法と比べ、点数が多い場合でも高速に動作するのが大きな利点です。

C++での実装例

それでは、実際のC++コードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
long long dist(long long xl, long long yl, long long xr, long long yr) {
    long long xd = xl - xr;
    long long yd = yl - yr;
    return xd * xd + yd * yd;
}
int solve(vector<vector<int>>& coordinates) {
    map<long long, long long> ytorightmostx;
    sort(coordinates.begin(), coordinates.end());
    long long ret = 1e18;
    for (auto& p : coordinates) {
        auto it = ytorightmostx.lower_bound(p[1] - sqrt(ret));
        while (it != ytorightmostx.end()) {
            long long yd = it->first - p[1];
            if (yd > 0 && yd * yd >= ret) {
                break;
            }
            auto nxt = it;
            nxt++;
            ret = min(ret, dist(p[0], p[1], it->second, it->first));
            long long xd = (it->second - p[0]);
            if (xd * xd >= ret) {
                ytorightmostx.erase(it);
            }
            it = nxt;
        }
        ytorightmostx[p[1]] = p[0];
    }
    return ret;
}
int main(){
    vector<vector<int>> coord = {{1, 2},{1, 4},{3, 5}};
    cout << solve(coord) << endl;
    return 0;
}

入力

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

出力

4

まとめ

本記事では、座標の集合から最も近い2点間の2乗距離を求める問題を、平面走査と std::map を組み合わせた効率的なアルゴリズムで解く方法を紹介しました。探索範囲を現在の最小距離に基づいて絞り込み、不要になった点を随時削除することで、O(n log n) の計算量を実現しています。同様の考え方は「最近接点対問題」全般に応用できるので、ぜひ参考にしてください。