概要

レーザーに反応する点は、ある直線を中心とする「幅 \(2D\) の帯」の中にある点です。
したがって、問題は「幅 \(2D\) の帯に入るセンサー数の最大値」を求める問題として考えます。

考察

レーザーの直線 \(\ell\) から距離 \(D\) 以下にある点は、\(\ell\) に平行な 2 本の直線で挟まれた帯の中にあります。

この帯の幅は、

\[ D + D = 2D \]

です。

つまり、レーザーの中心線そのものを考える代わりに、

幅 \(2D\) の帯に最大で何個の点を入れられるか

を考えればよいです。

ここで重要な観察があります。

最適な帯を考えたとき、その帯の境界線のうち少なくとも 1 本は、センサーの位置を 2 点以上通るようにできると考えられます。

なぜなら、もし境界線がどの点にも「しっかり当たっていない」なら、帯を少し平行移動したり回転したりしても含まれる点集合は変わりません。
最適な点集合を保ったまま帯の位置を調整していくと、最終的に境界線が 2 点を通るような状態にできます。

より幾何的には、含まれる点たちの凸包を考えると、最小幅の帯の境界線は凸包の辺に接するため、その境界線上に 2 点が乗ります。

したがって、候補としては、

2 つのセンサーを通る直線を「帯の境界線」として全探索する

だけで十分です。

注意点として、2 点を通る直線をレーザーの中心線として見るのではありません。
その直線を帯の片側の境界線とし、そこから片側に幅 \(2D\) の範囲にある点を数えます。

例えば、境界線からの距離が \(0\) 以上 \(2D\) 以下の点は、その真ん中の直線からの距離が必ず \(D\) 以下になります。

アルゴリズム

\(W = 2D\) とします。

2 つの異なるセンサー \(i, j\) を選び、それらを通る直線を考えます。

点 \(P_i = (X_i, Y_i)\)、\(P_j = (X_j, Y_j)\) とすると、

\[ dx = X_j - X_i \]

\[ dy = Y_j - Y_i \]

です。

別の点 \(P_k = (X_k, Y_k)\) について、

\[ ux = X_k - X_i \]

\[ uy = Y_k - Y_i \]

とします。

このとき、外積

\[ cross = dx \cdot uy - dy \cdot ux \]

を考えます。

外積には次の意味があります。

• \(cross > 0\) なら、点 \(P_k\) は直線の片側にある
• \(cross < 0\) なら、反対側にある
• \(cross = 0\) なら、直線上にある

また、点 \(P_k\) から直線 \(P_iP_j\) までの距離は、

\[ \frac{|cross|}{\sqrt{dx^2 + dy^2}} \]

です。

したがって、距離が \(W = 2D\) 以下である条件は、

\[ \frac{|cross|}{\sqrt{dx^2 + dy^2}} \leq W \]

です。

両辺を 2 乗して、

\[ cross^2 \leq W^2(dx^2 + dy^2) \]

と判定できます。

この判定を使って、各直線について次の 2 通りを数えます。

• 直線の正の側にあり、距離が \(W\) 以下の点の数
• 直線の負の側にあり、距離が \(W\) 以下の点の数

これは、帯が直線のどちら側に伸びるかを表しています。

すべてのセンサーの組 \((i, j)\) についてこれを試し、最大値を答えにします。

また、同じ座標に複数のセンサーがある場合があります。
すべて同じ座標にある場合など、異なる 2 点で直線を作れないケースもあるため、最初に同じ座標にあるセンサー数の最大値も答え候補に入れておきます。

計算量

• 時間計算量: \(O(N^3)\)
• 空間計算量: \(O(N)\)

\(N \leq 200\) なので、

\[ N^3 = 8,000,000 \]

程度であり、十分高速に実行できます。

実装のポイント

距離判定で平方根を使うと誤差が出る可能性があります。
そのため、次のように 2 乗した形で整数比較します。

\[ cross^2 \leq W^2(dx^2 + dy^2) \]

また、積が大きくなる可能性を考えて、コードでは __int128 を使って安全に計算しています。

__int128 limit = (__int128)W * W * len2;
__int128 sq = (__int128)cross * cross;

同じ座標の 2 点からは直線を定められないため、

if (dx == 0 && dy == 0) continue;

としてスキップします。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long D;
    cin >> N >> D;

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

    long long W = 2 * D;
    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++) {
            long long dx = X[j] - X[i];
            long long dy = Y[j] - Y[i];

            if (dx == 0 && dy == 0) continue;

            long long len2 = dx * dx + dy * dy;
            __int128 limit = (__int128)W * W * len2;

            int cnt_pos = 0, cnt_neg = 0;

            for (int k = 0; k < N; k++) {
                long long ux = X[k] - X[i];
                long long uy = Y[k] - Y[i];

                long long cross = dx * uy - dy * ux;
                __int128 sq = (__int128)cross * cross;

                if (sq <= limit) {
                    if (cross >= 0) cnt_pos++;
                    if (cross <= 0) cnt_neg++;
                }
            }

            ans = max(ans, cnt_pos);
            ans = max(ans, cnt_neg);
        }
    }

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

---

この解説は gpt-5.5-high によって生成されました。