C++で少なくともk個の点が円の内側に含まれる最小半径を求める方法

問題の概要

いくつかの点と整数 k が与えられたとき、中心が原点 (0, 0) にある円で少なくとも k 個の点を覆うための最小半径を求めます。例えば、点が (1, 1)、(-1, -1)、(1, -1) の3つで k = 3 の場合、すべての点を含むのに必要な半径は 2 となります。

解き方のアプローチ

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

1. 各点と原点 (0, 0) とのユークリッド距離を計算します。比較だけが目的であれば、平方根の計算を省略できるため、距離の二乗(x² + y²)をそのまま使うと計算コストを抑えられます。
2. 求めた距離(の二乗)を昇順にソートします。
3. ソート後のリストの k 番目の要素を返します。これが k 個の点を覆うために必要な最小半径(の二乗)に対応します。

原点からの距離が近い順に点を並べれば、k 番目に近い点の距離こそが、k 個の点をすべて円の内側に収めるための最小半径になる、という考え方です。

実装例(C++)

#include<iostream>
#include<algorithm>
using namespace std;
struct point{
   int x, y;
};
int minRadius(int k, point points[], int n) {
   int dist[n];
   for (int i = 0; i < n; i++)
   dist[i] = points[i].x * points[i].x + points[i].y * points[i].y;
   // 距離(の二乗)をソートする
   sort(dist, dist + n);
   return dist[k - 1];
}
int main() {
   int k = 3;
   point points[] = {{1, 1}, {-1, -1}, {1, -1}};
   int n = sizeof(points)/sizeof(points[0]);
   cout << "Minimum radius: " << minRadius(k, points, n) << endl;
}

出力結果

Minimum radius: 2

計算量について

各点の距離計算には O(n)、ソートには O(n log n) の時間がかかるため、このアルゴリズム全体の時間計算量は O(n log n) となります。追加で使用する配列の分、空間計算量は O(n) です。点の数が多い場合でも、ソートベースのシンプルな手法として十分実用的な性能を発揮します。