E - レーザーポインターの実験 / Laser Pointer Experiment Editorial by admin
gpt-5.5-highOverview
The problem of counting points within distance \(D\) from a laser beam can be rephrased as finding the maximum number of points contained in a strip of width \(2D\).
Analysis
If we treat the laser beam as the centerline, the sensors that respond are the points within a distance of \(D\) from this centerline.
This is equivalent to counting the points contained in a strip of width
\(W = 2D\)
formed by drawing boundary lines at a distance \(D\) on both sides of the centerline.
In other words, the problem becomes:
Place a strip of width \(W\) bounded by two parallel lines on the plane, and maximize the weighted number of points contained within it.
If there are multiple sensors at the same coordinates, they will always respond at the same time, so we can group them by coordinates and treat them as a single point with a “weight”.
Simply trying all “lines passing through 2 points” is not sufficient.
For example, if \(D=1\) and the points are at \((0,0)\) and \((0,2)\), the optimal laser beam is \(y=1\), but this line does not pass through either point.
Therefore, instead of focusing on the laser beam itself, we focus on the boundary lines of the strip of width \(W\).
An optimal strip can be adjusted (by translation and rotation) without decreasing the number of points it contains, so that it satisfies one of the following configurations:
- At least 2 points lie on one of the boundary lines.
- At least 1 point lies on each of the two boundary lines.
Therefore, it is sufficient to enumerate only these two types of candidate configurations.
Algorithm
First, we group sensors at the same coordinates.
Hereinafter, each point \(P_i=(X_i,Y_i)\) is treated as having a weight \(w_i\).
1. The Case \(D=0\)
When \(D=0\), the width of the strip is \(0\), so we just need to find the maximum sum of weights of collinear points.
Using each point \(P_i\) as a reference, we normalize the direction vectors to all other points.
For a direction vector \((dx,dy)\), we divide it by
\(g=\gcd(|dx|,|dy|)\)
and use
\((dx/g,dy/g)\).
Note that opposite directions represent the same line, so we unify their signs.
We sum the weights for each direction and update the maximum value.
2. The Case \(D>0\)
Let the width be
\(W=2D\).
Case A: 2 points lie on one boundary line
Suppose points \(P_i\) and \(P_j\) lie on the same boundary line.
If the direction vector of this boundary line is
\((dx,dy)=P_j-P_i\),
then its normal vector is, for example,
\((dy,-dx)\).
Let the normal vector be \(n=(n_x,n_y)\).
For any point \(P_k\), consider
\(s=n_x(X_k-X_i)+n_y(Y_k-Y_i)\).
This quantity represents how far the point \(P_k\) is from the boundary line in the normal direction.
The condition for point \(P_k\) to be inside the strip is, for one side of the boundary line,
\(0 \leq s \leq W|n|\)
or, for the other side,
\(-W|n| \leq s \leq 0\).
To avoid square roots, in the implementation, we check this using
\(s^2 \leq W^2(n_x^2+n_y^2)\).
Since the number of points depends on which side of the boundary line the strip is placed, we count both cases and take the maximum.
Case B: 1 point lies on each of the two boundary lines
Suppose point \(P_i\) lies on one boundary line and point \(P_j\) lies on the other boundary line.
In this case, let the vector from \(P_i\) to \(P_j\) be
\(v=(dx,dy)\)
and let
\(r^2=dx^2+dy^2\).
For the two points to lie on opposite boundaries of a strip of width \(W\), we must have at least
\(r > W\).
The normal direction is the direction where the projection of \(v\) onto it is exactly \(W\).
When \(r > W\), there are two such directions.
If we let the vector perpendicular to \(v\) be
\(q=(-dy,dx)\),
then the vector proportional to the normal direction can be expressed as
\(h_\pm = Wv \pm \sqrt{r^2-W^2}q\).
This vector is scaled to have a length of \(r^2\) and satisfies
\(h_\pm \cdot v = Wr^2\).
For any point \(P_k\), letting \(u=P_k-P_i\), the condition for it to be inside the strip is
\(0 \leq h_\pm \cdot u \leq Wr^2\).
In the implementation, the check is performed using
\(h_\pm \cdot u = W(v\cdot u) \pm \sqrt{r^2-W^2}(q\cdot u)\).
Since the square root may not be an integer, instead of using floating-point numbers, we perform an exact comparison by squaring the terms.
We test all candidates of these two types and output the maximum value.
Complexity
Let \(M\) be the number of unique coordinates after grouping duplicates.
We have \(M \leq N\).
- Time Complexity: \(O(M^3)\)
- Space Complexity: \(O(M^2)\)
Since \(N \leq 200\), an \(O(N^3)\) algorithm is fast enough to pass within the time limit.
Implementation Details
Group sensors at the same coordinates and treat them as a single point with a weight.
If \(D=0\), handle it separately as the problem of finding the maximum number of collinear points.
Avoid square roots and floating-point numbers in distance checks; use integer arithmetic for comparisons.
Since points on the boundary of the strip also respond, use \(\leq\) for all inequalities.
If the answer reaches \(N\), we can terminate early because it cannot be improved further.
Source Code
import sys
import math
from collections import defaultdict
def count_lower_both(nx, ny, dxs, dys, ws, W2):
lim = W2 * (nx * nx + ny * ny)
cp = 0
cn = 0
m = len(ws)
for i in range(m):
dot = nx * dxs[i] + ny * dys[i]
sq = dot * dot
if sq <= lim:
w = ws[i]
if dot >= 0:
cp += w
if dot <= 0:
cn += w
return cp if cp >= cn else cn
def count_upper_both(dx, dy, r2, dxs, dys, ws, W, W2):
mm = r2 - W2
c_lim = W * r2
qx = -dy
qy = dx
m = len(ws)
root = math.isqrt(mm)
if root * root == mm:
cp = 0
cn = 0
for i in range(m):
ux = dxs[i]
uy = dys[i]
a = W * (dx * ux + dy * uy)
b = qx * ux + qy * uy
w = ws[i]
v = a + b * root
if 0 <= v <= c_lim:
cp += w
v = a - b * root
if 0 <= v <= c_lim:
cn += w
return cp if cp >= cn else cn
cp = 0
cn = 0
for i in range(m):
ux = dxs[i]
uy = dys[i]
a = W * (dx * ux + dy * uy)
b = qx * ux + qy * uy
ac = a - c_lim
wt = ws[i]
b2m = -1
a2 = -1
ac2 = -1
ok = True
if a < 0:
if b < 0:
ok = False
else:
b2m = b * b * mm
a2 = a * a
if b2m < a2:
ok = False
else:
if b < 0:
b2m = b * b * mm
a2 = a * a
if a2 < b2m:
ok = False
if ok:
if ac > 0:
if b > 0:
ok = False
else:
if b2m < 0:
b2m = b * b * mm
ac2 = ac * ac
if ac2 > b2m:
ok = False
else:
if b > 0:
if b2m < 0:
b2m = b * b * mm
ac2 = ac * ac
if b2m > ac2:
ok = False
if ok:
cp += wt
ok = True
if a < 0:
if b > 0:
ok = False
else:
if b2m < 0:
b2m = b * b * mm
if a2 < 0:
a2 = a * a
if b2m < a2:
ok = False
else:
if b > 0:
if b2m < 0:
b2m = b * b * mm
if a2 < 0:
a2 = a * a
if a2 < b2m:
ok = False
if ok:
if ac > 0:
if b < 0:
ok = False
else:
if b2m < 0:
b2m = b * b * mm
if ac2 < 0:
ac2 = ac * ac
if ac2 > b2m:
ok = False
else:
if b < 0:
if b2m < 0:
b2m = b * b * mm
if ac2 < 0:
ac2 = ac * ac
if b2m > ac2:
ok = False
if ok:
cn += wt
return cp if cp >= cn else cn
def main():
input = sys.stdin.readline
N, D = map(int, input().split())
cnt = defaultdict(int)
for _ in range(N):
x, y = map(int, input().split())
cnt[(x, y)] += 1
pts = list(cnt.keys())
ws = [cnt[p] for p in pts]
xs = [p[0] for p in pts]
ys = [p[1] for p in pts]
M = len(pts)
if M == 1:
print(N)
return
ans = max(ws)
dxmat = [[xs[j] - xs[i] for j in range(M)] for i in range(M)]
dymat = [[ys[j] - ys[i] for j in range(M)] for i in range(M)]
if D == 0:
for i in range(M):
mp = defaultdict(int)
dxs = dxmat[i]
dys = dymat[i]
for j in range(M):
if i == j:
continue
dx = dxs[j]
dy = dys[j]
g = math.gcd(abs(dx), abs(dy))
dx //= g
dy //= g
if dx < 0 or (dx == 0 and dy < 0):
dx = -dx
dy = -dy
mp[(dx, dy)] += ws[j]
best = ws[i]
for v in mp.values():
cur = ws[i] + v
if cur > best:
best = cur
if best > ans:
ans = best
print(ans)
return
W = 2 * D
W2 = W * W
for i in range(M):
dxs = dxmat[i]
dys = dymat[i]
normals = set()
for j in range(M):
if i == j:
continue
dx = dxs[j]
dy = dys[j]
g = math.gcd(abs(dx), abs(dy))
nx = dy // g
ny = -dx // g
if nx < 0 or (nx == 0 and ny < 0):
nx = -nx
ny = -ny
normals.add((nx, ny))
for nx, ny in normals:
v = count_lower_both(nx, ny, dxs, dys, ws, W2)
if v > ans:
ans = v
if ans == N:
print(ans)
return
for j in range(M):
if i == j:
continue
dx = dxs[j]
dy = dys[j]
r2 = dx * dx + dy * dy
if r2 > W2:
v = count_upper_both(dx, dy, r2, dxs, dys, ws, W, W2)
if v > ans:
ans = v
if ans == N:
print(ans)
return
print(ans)
if __name__ == "__main__":
main()
This editorial was generated by gpt-5.5-high.
posted:
last update: