Overview

This problem asks us to find a line on a plane that maximizes the number of points (sensors) within a distance of \(D\) from it, out of \(N\) given points.

Although there are infinitely many ways to draw a line, we can narrow down the candidates by using the property: “An optimal line always exists among a set of representative lines (candidates) satisfying specific conditions.” This allows us to solve the problem correctly in \(O(N^3)\) time complexity.

---

Analysis

1. How to narrow down the candidate lines?

Suppose we have chosen an optimal line. Let us consider translating or rotating this line without decreasing the number of covered sensors.

The region within distance \(D\) of a line can be viewed as a “strip of width \(2D\)”. We want to include as many points as possible within this strip.

1. If we translate the strip, eventually at least one sensor will hit the boundary of the strip (at a distance of \(D\) from the line).
2. Keeping that sensor fixed, if we rotate the strip, another sensor will eventually hit the boundary of the strip.

When we reach such a state where no further movement is possible (an extremal state), the line satisfies the condition: “The distance from two sensors \(i\) and \(j\) to the line is exactly \(D\).”

Therefore, for every pair of sensors \(i, j\), we can enumerate all “lines whose distance to both points is exactly \(D\)”. If we count the number of sensors within distance \(D\) for each of these lines, the line that yields the maximum count is guaranteed to be among them.

2. Classification of lines at distance exactly \(D\) from two points

Lines whose distance to both sensors \(i\) and \(j\) is exactly \(D\) can be classified into the following two cases based on their relative positions:

Case 1: The two sensors are on the same side of the line

In this case, the line is parallel to the line segment connecting \(i\) and \(j\). Such a line is obtained by translating the segment \(ij\) by \(D\) in the normal direction. There are two such candidate lines.

Case 2: The two sensors are on opposite sides of the line

In this case, the line passes between \(i\) and \(j\). For such a line to exist, the distance between the two points \(i\) and \(j\) must be at least \(2D\). The lines satisfying this condition pass through the midpoint of the segment \(ij\). There are two such candidate lines.

---

Algorithm

For all pairs of sensors \((i, j)\) (\(O(N^2)\) pairs), we find the lines corresponding to the two cases above, and for each line, we count the number of sensors within distance \(D\) in \(O(N)\) time.

Case 1 Check (Integer Geometry)

Consider a direction vector parallel to the line passing through sensors \(i(X_i, Y_i)\) and \(j(X_j, Y_j)\). Let \(A = Y_j - Y_i\) and \(B = X_i - X_j\). Any parallel line can be represented as \(AX + BY + C = 0\).

Let the reference value be \(C_{base} = -(AX_i + BY_i)\). For any point \(k\), using the value \(val = AX_k + BY_k + C_{base}\), the condition for point \(k\) to be within distance \(D\) from the line can be formulated as follows (we check using squared values to avoid square roots):

• If the line is at distance \(D\) from \(i, j\) in the positive direction: \(val \ge 0\) and \(val^2 \le 4 D^2 (A^2 + B^2)\)
• If the line is at distance \(D\) from \(i, j\) in the negative direction: \(val \le 0\) and \(val^2 \le 4 D^2 (A^2 + B^2)\)

This allows us to perform precise checks without floating-point operations (which can cause precision errors).

Case 2 Check (Floating-Point Geometry)

Let the squared distance between the two points \(i, j\) be \(L^2 = (X_j - X_i)^2 + (Y_j - Y_i)^2\). A satisfying line exists if and only if \(L^2 \ge 4D^2\).

Using trigonometric ratios or the Pythagorean theorem to find the normal vector of the line, the condition for whether point \(k\) satisfies the requirement reduces to the following expressions in the code:

• \(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}\)

Then, for each of the two candidate lines, we check if: \(|A \pm B C| \le 2D L^2\) holds (under a threshold that accounts for floating-point precision errors).

---

Complexity

• Time Complexity: \(O(N^3)\) There are \(O(N^2)\) ways to choose a pair of sensors. Since we check the distance to all \(N\) sensors for each pair, the overall time complexity is \(O(N^3)\). With \(N \le 200\), the number of operations is around \(N^3 \approx 8 \times 10^6\), which is well within the time limit (usually 2 seconds).

• Space Complexity: \(O(N)\) Since we only need arrays to store the coordinates of the sensors, the space complexity is \(O(N)\), which is extremely memory efficient.

---

Key Implementation Details

1. Handling Sensors at the Same Coordinates: There may be cases where multiple sensors exist at the exact same coordinates in the input. When selecting a pair \((i, j)\), we must skip pairs with identical coordinates. Additionally, we should initialize our answer with the maximum number of sensors sharing the same coordinates.

2. Handling \(N=1\): When \(N=1\), we cannot form any pairs. We should handle this corner case separately by outputting 1 and terminating.

3. Mitigating Floating-Point Precision Errors: In Case 2, since we use the square root function (sqrt), minor computational errors are inevitable. To prevent incorrect judgments due to precision issues, we should include a small tolerance value (epsilon), such as 1e-8, in our comparisons.

   Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-high.