C++で原点に最も近いK個の点を見つけるアルゴリズムを解説

平面上に複数の点が与えられたとき、その中から原点(0, 0)に最も近いK個の点を求める問題を考えてみましょう。

例として、点 (3, 3)、(5, -1)、(-2, 4) の3点が与えられ、K = 2 とします。このとき原点に最も近い2点は (3, 3) と (-2, 4) になります。

解決のアプローチ

この問題は次の手順で解くことができます。

1. 各点についてユークリッド距離を計算します。原点からの距離は √(x² + y²) で表されますが、大小比較だけであれば平方根の計算は不要なので、x² + y² の値をそのまま使えば十分です。
2. 距離を基準に点のリストをソートします。
3. ソート後のリストから先頭のK個の要素を取り出します。これが原点に最も近いK個の点となります。

C++での実装例

#include<iostream>
#include<algorithm>
using namespace std;

class Point {
    private:
        int x, y;
    public:
        Point(int x = 0, int y = 0) {
            this->x = x;
            this->y = y;
        }
        void display() {
            cout << "(" << x << ", " << y << ")";
        }
    friend bool comparePoints(Point &p1, Point &p2);
};

// 原点からの距離を比較する関数
bool comparePoints(Point &p1, Point &p2) {
    float dist1 = (p1.x * p1.x) + (p1.y * p1.y);
    float dist2 = (p2.x * p2.x) + (p2.y * p2.y);
    return dist1 < dist2;
}

// 原点に最も近いK個の点を出力する関数
void closestKPoints(Point points[], int n, int k) {
    sort(points, points + n, comparePoints);
    for(int i = 0; i < k; i++) {
        points[i].display();
        cout << endl;
    }
}

int main() {
    Point points[] = {{3, 3}, {5, -1}, {-2, 4}};
    int n = sizeof(points) / sizeof(points[0]);
    int k = 2;
    closestKPoints(points, n, k);
}

実行結果

(3, 3)
(-2, 4)

コードのポイント

• comparePoints関数: 2つの点それぞれの x² + y² を計算し、どちらが原点に近いかを判定します。friend 宣言により、クラスのprivateメンバである x・y 座標にアクセスできるようにしています。
• sort関数: STLの std::sort を使い、カスタム比較関数に基づいて点を昇順に並べ替えます。
• 計算量: ソートに O(n log n) の時間がかかります。データ数が非常に多い場合は、ヒープ（優先度付きキュー）を使うことで O(n log k) まで効率化することも可能です。

このように、ソートとカスタム比較関数を組み合わせるだけで、「原点に最も近いK個の点」をシンプルに求めることができます。