C++で円の内部に含まれる点の数を求めるクエリ処理｜効率的な解法を解説

この問題では、2次元平面上に存在するn個の点が与えられます。各点の座標は(x, y)です。私たちのタスクは複数のクエリを処理することです。各クエリでは整数Rが与えられ、原点(0, 0)を中心とする半径Rの円の内部に含まれる点の個数を求めます。

問題の概要

各クエリに対して、与えられたn個の点のうち、中心が原点(0, 0)、半径がRの円（円周の内側）に含まれる点の総数を出力します。

例で問題を理解しよう

入力

n = 5
2 1
1 2
3 3
-1 0
-2 -2
Query 1: 2

出力

1

説明 − このクエリで与えられた半径は2です。点(-1, 0)だけが円の内部にあり、残りの点はすべて円の外部にあります。

円の方程式は (x₂ − x₁)² + (y₂ − y₁)² = r² です。したがって、中心が(0, 0)の円の内部に点(x, y)が含まれるためには、x² + y² ≤ r² を満たす必要があります。

この問題を解く最もシンプルなアプローチは、各クエリごとにすべての点を走査し、上記の式を使ってその点が円周の内側にあるかどうかを判定する方法です。

この解法の動作を示すプログラム：

例

#include <iostream>
using namespace std;

int solveQuery(int x[], int y[], int n, int R) {
    int count = 0;
    for(int i = 0; i < n; i++){
        if(((x[i]*x[i]) + (y[i]*y[i])) <= (R*R))
            count++;
    }
    return count;
}
int main() {
    int x[] = { 2, 1, 3, -1, -2 };
    int y[] = { 1, 2, 3, 0, -2 };
    int n = sizeof(x) / sizeof(x[0]);
    int Q = 2;
    int query[] = {4, 2};
    for(int i = 0; i < Q; i++)
        cout<<"クエリ "<<(i+1)<<": 円の内部にある点の数は "<<solveQuery(x, y, n, query[i])<<"\n";
    return 0;
}

出力

クエリ 1: 円の内部にある点の数は 4
クエリ 2: 円の内部にある点の数は 1

このアプローチにおける時間計算量はO(n × Q)です。これは、各クエリに対してn個すべての点についてx² + y²の値を計算し直す必要があるためです。

そこで、より効率的な解法として、あらかじめすべてのn個の点についてx² + y²の値を計算し、配列に格納しておく方法が有効です。この配列はすべてのクエリで共通して使い回せます。さらに最適化するために、配列を事前にソートしておき、二分探索によって「円の外側となる最初の要素」の位置を特定すれば、各クエリの処理を高速化できます。前計算とソートにO(n log n)、以降の各クエリはO(log n)で処理可能です。

この解法の動作を示すプログラム：

例

#include <bits/stdc++.h>
using namespace std;

int solveQuery(int points[], int n, int rad) {
    int l = 0, r = n - 1;
    while ((r - l) > 1) {
        int mid = (l + r) / 2;
        if (points[mid] > (rad * rad))
            r = mid - 1;
        else
            l = mid;
    }
    if ((sqrt(points[l])) > (rad * 1.0))
        return 0;
    else if ((sqrt(points[r])) <= (rad * 1.0))
        return r + 1;
    else
        return l + 1;
}

int main() {
    int n = 5;
    int point[n][2] = { {2, 1}, {1, 2}, {3, 3}, {-1, 0}, {-2, -2} };
    int Q = 2;
    int query[] = {4, 2};
    int points[n];
    // 各点の原点からの距離の2乗を前計算
    for (int i = 0; i < n; i++)
        points[i] = (point[i][0]*point[i][0]) + (point[i][1]*point[i][1]);
    sort(points, points + n);
    for(int i = 0; i < Q; i++)
        cout<<"クエリ "<<(i+1)<<": 円の内部にある点の数は "<<solveQuery(points, n, query[i])<<"\n";
    return 0;
}

出力

クエリ 1: 円の内部にある点の数は 4
クエリ 2: 円の内部にある点の数は 1