Overview

The problem asks us to draw a single straight line on a plane to maximize the number of sensors (points) whose distance to the line is at most \(D\).

Analysis

When a line is drawn, the points whose distance to the line is at most \(D\) correspond to the points that fall within an interval of width \(2D\) centered at the line’s position when projected onto the direction perpendicular to the line (the normal direction). Therefore, this problem can be reduced to: “find the maximum number of points contained in an interval of length at most \(2D\) when the points are projected onto some direction.”

Although there are infinitely many directions (normal vectors) to project onto, we do not need to check all of them. If we imagine gradually changing the angle of the projection from the optimal direction, there will always be a moment when a point is about to leave the interval of width \(2D\), or when a new point is about to enter the interval. Such a moment occurs in a direction that satisfies one of the following conditions: 1. A direction perpendicular to the line connecting two points \(i\) and \(j\) (at this moment, the projection values of the two points coincide). 2. A direction where the difference between the projection values of two points \(i\) and \(j\) is exactly \(2D\).

Thus, by exhaustively searching the candidate normal vectors generated from these two conditions, we are guaranteed to find the optimal solution.

Algorithm

1. Generating Candidate Normal Vectors: For every pair of points \((i, j)\), consider the vector \((dx, dy) = (X_i - X_j, Y_i - Y_j)\).
   • Condition 1: A direction perpendicular to the vector \((dx, dy)\). As a unit vector, this is \((a, b) = \left(\frac{dy}{L}, \frac{-dx}{L}\right)\) (where \(L = \sqrt{dx^2 + dy^2}\)).
   • Condition 2: A direction where the difference in projection values is \(2D\). Solving for \((a, b)\) such that \(a \cdot dx + b \cdot dy = 2D\) and \(a^2 + b^2 = 1\) yields solutions when \(L \ge 2D\). The solutions can be calculated using trigonometric functions; in the code, to reduce precision errors, the calculation is performed by dividing by the sum of squares \(L^2\).
2. Projection and Two-Pointer Technique: For each candidate vector \((a, b)\), calculate the projection values \(p_k = aX_k + bY_k\) for all points, and sort them. Perform the two-pointer technique on the sorted array to find the maximum number of elements in an interval where the difference between the maximum and minimum values is at most \(2D\). The maximum number of elements over all candidates is the answer.

Complexity

• Time Complexity: \(O(N^3 \log N)\) There are \(O(N^2)\) candidate normal vectors, and for each candidate, sorting the projection values takes \(O(N \log N)\) time. Since \(N \le 200\), this is sufficiently fast.
• Space Complexity: \(O(N^2)\) Space is required to store the candidate vectors.

Implementation Details

• Handling Floating-Point Precision Errors: When comparing the difference in projection values in the two-pointer technique, adding a small constant eps (e.g., \(10^{-9}\)), as in proj[r] - proj[l] <= 2 * D + eps, prevents missing valid intervals due to precision errors.

• Boundary for Condition 2: If the distance \(L\) between two points is strictly less than \(2D\), it is impossible to make the difference in projection values equal to \(2D\), so this calculation must be skipped. In the code, this is checked using L2 >= V_2D * V_2D.

  Source Code

import sys
import math

def solve():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    points = [tuple(map(int, input().split())) for _ in range(N)]

    candidates = [(1.0, 0.0)]
    eps = 1e-9
    V_2D = 2.0 * D

    for i in range(N):
        xi, yi = points[i]
        for j in range(i + 1, N):
            xj, yj = points[j]
            dx = xi - xj
            dy = yi - yj
            L2 = dx * dx + dy * dy
            
            if L2 > 0:
                L = math.sqrt(L2)
                a = dy / L
                b = -dx / L
                candidates.append((a, b))
                
                if V_2D > 0 and L2 >= V_2D * V_2D:
                    norm = math.sqrt(L2 - V_2D * V_2D)
                    a1 = (V_2D * dx + norm * dy) / L2
                    b1 = (V_2D * dy - norm * dx) / L2
                    candidates.append((a1, b1))

    ans = 0
    for a, b in candidates:
        proj = [a * x + b * y for x, y in points]
        proj.sort()
        
        r = 0
        for l in range(N):
            while r < N and proj[r] - proj[l] <= V_2D + eps:
                r += 1
            if r - l > ans:
                ans = r - l
            
    print(ans)

solve()

This editorial was generated by or-glm5.2-high.