Overview

Points that react to the laser are those located within a “strip of width \(2D\)” centered on some line.
Therefore, we can frame this problem as finding the maximum number of sensors that can be contained within a strip of width \(2D\).

Analysis

Points within distance \(D\) of the laser line \(\ell\) lie inside a strip bounded by two lines parallel to \(\ell\).

The width of this strip is:

\[ D + D = 2D \]

In other words, instead of considering the centerline of the laser itself, we can consider:

What is the maximum number of points we can include in a strip of width \(2D\)?

Here is an important observation.

When considering an optimal strip, we can assume that at least one of its boundary lines passes through at least two sensor positions.

This is because if the boundary lines do not “touch” any points tightly, we can translate or rotate the strip slightly without changing the set of included points.
By adjusting the position of the strip while preserving the optimal set of points, we can eventually reach a state where a boundary line passes through two points.

More geometrically, if we consider the convex hull of the included points, the boundary lines of the minimum-width strip will touch an edge of the convex hull, meaning two points will lie on that boundary line.

Therefore, as candidates, it is sufficient to:

Search all lines passing through two sensors as the “boundary line of the strip”.

Note that we do not treat the line passing through the two points as the centerline of the laser.
Instead, we treat that line as one of the boundaries of the strip, and count the points within a width of \(2D\) on one side of it.

For example, points whose distance from the boundary line is between \(0\) and \(2D\) will always have a distance of at most \(D\) from the centerline of the strip.

Algorithm

Let \(W = 2D\).

Choose two different sensors \(i\) and \(j\), and consider the line passing through them.

Let the points be \(P_i = (X_i, Y_i)\) and \(P_j = (X_j, Y_j)\):

\[ dx = X_j - X_i \]

\[ dy = Y_j - Y_i \]

For another point \(P_k = (X_k, Y_k)\), let:

\[ ux = X_k - X_i \]

\[ uy = Y_k - Y_i \]

Now, consider the cross product:

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

The cross product has the following geometric meanings:

• If \(cross > 0\), the point \(P_k\) lies on one side of the line.
• If \(cross < 0\), it lies on the opposite side.
• If \(cross = 0\), it lies on the line.

Also, the distance from point \(P_k\) to the line \(P_iP_j\) is:

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

Therefore, the condition for the distance to be at most \(W = 2D\) is:

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

By squaring both sides, we can check this condition as:

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

Using this condition, we count the following two cases for each line:

• The number of points on the positive side of the line with a distance of at most \(W\).
• The number of points on the negative side of the line with a distance of at most \(W\).

This represents whether the strip extends to the positive side or the negative side of the line.

We try this for all pairs of sensors \((i, j)\) and take the maximum value as the answer.

Additionally, multiple sensors may share the exact same coordinates.
In cases where all sensors are at the same coordinates, we cannot form a line with two distinct points. Therefore, we should initialize our answer candidate with the maximum number of sensors at the same coordinates.

Complexity

• Time Complexity: \(O(N^3)\)
• Space Complexity: \(O(N)\)

Since \(N \leq 200\),

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

which is around \(8,000,000\) operations, and it runs fast enough.

Implementation Details

Using square roots for distance checks can introduce precision errors.
Therefore, we compare them as integers in their squared forms as follows:

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

Also, considering that the product can become very large, we use __int128 in the code to calculate safely.

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

Since we cannot define a line from two points at the same coordinates, we skip them with:

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

Source Code

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

---

This editorial was generated by gpt-5.5-high.