概要

この問題は、平面上の \(N\) 個の点（センサー）のうち、選んだ直線からの距離が \(D\) 以下であるものの個数を最大化する問題です。

直線の引き方は無限にありますが、「最適な直線は、特定の条件を満たす代表的な直線（候補）の中に必ず存在する」という性質を利用して候補を絞り込むことで、 \(O(N^3)\) の時間計算量で正しく解くことができます。

---

考察

1. 直線の候補をどのように絞り込むか？

最適な直線を1つ選んだとします。この直線を、カバーするセンサーの数を減らさないように平行移動したり回転したりすることを考えます。

直線から距離 \(D\) 以内の領域は、「幅 \(2D\) の帯状の領域」とみなすことができます。この帯の中にできるだけ多くの点を含めたいわけです。

1. 帯を平行移動させていくと、やがて帯の境界（直線から距離 \(D\) の位置）に少なくとも1つのセンサーがぶつかります。
2. そのセンサーを固定したまま帯を回転させていくと、さらにもう1つのセンサーが帯の境界にぶつかります。

このようにして、これ以上動かせない状態（極値）に達したとき、直線は「2つのセンサー \(i, j\) からの距離がちょうど \(D\) である」という条件を満たします。

したがって、任意の2つのセンサー \(i, j\) のペアについて、「両方からの距離がちょうど \(D\) になるような直線」をすべて列挙し、それぞれの直線について距離 \(D\) 以下のセンサーの個数を数え上げれば、その中に必ず最大値を与える直線が含まれます。

2. 2点からの距離がちょうど \(D\) である直線の分類

2つのセンサー \(i, j\) からの距離がともに \(D\) である直線は、位置関係によって以下の2つのケースに分類できます。

ケース1：2つのセンサーが直線の同じ側にある場合

このとき、直線は \(i\) と \(j\) を結ぶ線分に平行になります。 このような直線は、線分 \(ij\) を法線方向に \(D\) だけ平行移動したものであり、2本の直線が考えられます。

ケース2：2つのセンサーが直線の反対側にある場合

このとき、直線は \(i\) と \(j\) の間を通ります。 このような直線が存在するためには、2点 \(i, j\) 間の距離が \(2D\) 以上である必要があります。条件を満たす直線は、線分 \(ij\) の中点を通るようなものであり、2本の直線が考えられます。

---

アルゴリズム

すべてのセンサーのペア \((i, j)\) （ \(O(N^2)\) 通り）について、上記の2つのケースにおける直線を求め、各直線について距離が \(D\) 以下となるセンサーの個数を \(O(N)\) でカウントします。

ケース1の判定（整数幾何）

センサー \(i(X_i, Y_i)\) と \(j(X_j, Y_j)\) を通る直線に平行な方向ベクトルを考えます。 \(A = Y_j - Y_i\), \(B = X_i - X_j\) とおくと、平行な直線は \(AX + BY + C = 0\) と表せます。

基準となる \(C_{base} = -(AX_i + BY_i)\) とすると、任意の点 \(k\) における値 \(val = AX_k + BY_k + C_{base}\) を用いて、点 \(k\) が直線から距離 \(D\) 以下である条件は以下のように整理できます（平方根を避けるため、2乗の形で判定します）。

• 直線が \(i, j\) からプラス方向に \(D\) 離れている場合： \(val \ge 0\) かつ \(val^2 \le 4 D^2 (A^2 + B^2)\)
• 直線が \(i, j\) からマイナス方向に \(D\) 離れている場合： \(val \le 0\) かつ \(val^2 \le 4 D^2 (A^2 + B^2)\)

これにより、小数演算（誤差の原因）を排除して正確に判定できます。

ケース2の判定（浮動小数点数幾何）

2点 \(i, j\) 間の距離の2乗を \(L^2 = (X_j - X_i)^2 + (Y_j - Y_i)^2\) とします。 \(L^2 \ge 4D^2\) のときのみ、条件を満たす直線が存在します。

直線の法線ベクトルを求めるために三角比やピタゴラスの定理を用いると、点 \(k\) が条件を満たすかどうかの判定式は、コード中の以下の式に帰着されます。

• \(w_x = X_j - X_i\), \(w_y = Y_j - Y_i\)
• \(d_x = 2X_k - X_i - X_j\), \(d_y = 2Y_k - Y_i - Y_j\)
• \(A = 2D(w_x d_x + w_y d_y)\), \(B = w_x d_y - w_y d_x\), \(C = \sqrt{L^2 - 4D^2}\)

このとき、2つの直線の候補それぞれについて、 \(|A \pm B C| \le 2D L^2\) が（浮動小数点の誤差を考慮した閾値のもとで）成り立つかを判定します。

---

計算量

• 時間計算量: \(O(N^3)\) センサーのペアの選び方が \(O(N^2)\) 通りあり、それぞれのペアに対してすべてのセンサー（ \(N\) 個）との距離を判定するため、全体の計算量は \(O(N^3)\) となります。 \(N \le 200\) であるため、 \(N^3 \approx 8 \times 10^6\) 回の計算となり、実行時間制限（通常2秒）に対して十分に高速です。

• 空間計算量: \(O(N)\) センサーの座標を格納する配列のみを使用するため、空間計算量は \(O(N)\) となり、非常に省メモリです。

---

実装のポイント

1. 同一座標のセンサーの考慮: 入力として全く同じ座標に複数のセンサーが存在する場合があります。ペア \((i, j)\) を選ぶ際、同じ座標のペアはスキップする必要があります。また、初期値として「同一座標に存在するセンサーの最大数」を答えの初期値に設定しておく必要があります。

2. \(N=1\) のハンドリング: \(N=1\) のときはペアを作ることができないため、コーナーケースとして個別に 1 を出力して終了します。

3. 浮動小数点数の誤差対策: ケース2では平方根（sqrt）を使用するため、どうしてもわずかな計算誤差が生じます。そのため、判定の際には 1e-8 などの小さな値を許容値（エプシロン）として加えることで、誤差による判定ミスを防いでいます。

   ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;

    vector<long long> X(N), Y(N);
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> Y[i];
    }

    if (N == 1) {
        cout << 1 << "\n";
        return 0;
    }

    int ans = 1;
    // 同一座標のセンサーを考慮して、初期値を設定
    for (int i = 0; i < N; ++i) {
        int cnt = 0;
        for (int j = 0; j < N; ++j) {
            if (X[i] == X[j] && Y[i] == Y[j]) {
                cnt++;
            }
        }
        ans = max(ans, cnt);
    }

    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (X[i] == X[j] && Y[i] == Y[j]) continue;

            // ケース1: 2つのセンサーが直線の同じ側にある場合
            {
                long long A = Y[j] - Y[i];
                long long B = X[i] - X[j];
                long long C = -(A * X[i] + B * Y[i]);
                long long L2 = A * A + B * B;
                long long limit = 4 * D * D * L2;

                int cnt_up = 0;
                int cnt_down = 0;
                for (int k = 0; k < N; ++k) {
                    long long val = A * X[k] + B * Y[k] + C;
                    if (val >= 0 && val * val <= limit) {
                        cnt_up++;
                    }
                    if (val <= 0 && val * val <= limit) {
                        cnt_down++;
                    }
                }
                ans = max({ans, cnt_up, cnt_down});
            }

            // ケース2: 2つのセンサーが直線の反対側にある場合
            long long wx = X[j] - X[i];
            long long wy = Y[j] - Y[i];
            long long L2 = wx * wx + wy * wy;
            if (L2 >= 4 * D * D) {
                double C = sqrt((double)(L2 - 4 * D * D));
                int cnt1 = 0;
                int cnt2 = 0;
                double target = 2.0 * D * L2 + 1e-8;
                for (int k = 0; k < N; ++k) {
                    long long dx = 2 * X[k] - X[i] - X[j];
                    long long dy = 2 * Y[k] - Y[i] - Y[j];
                    long long A = 2 * D * (wx * dx + wy * dy);
                    long long B = wx * dy - wy * dx;

                    double val1 = A + B * C;
                    double val2 = A - B * C;

                    if (abs(val1) <= target) {
                        cnt1++;
                    }
                    if (abs(val2) <= target) {
                        cnt2++;
                    }
                }
                ans = max({ans, cnt1, cnt2});
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。