E - レーザーポインターの実験 / Laser Pointer Experiment Editorial by admin
gpt-5.5-high概要
レーザー光線から距離 \(D\) 以下にある点を数える問題は、幅 \(2D\) の帯状領域（ストリップ）に含まれる点の最大個数を求める問題と言い換えられます。
考察
レーザー光線を中心線とすると、反応するセンサーはその中心線から距離 \(D\) 以下にある点です。
これは、中心線の両側に距離 \(D\) の境界線を引いた、幅
\(W = 2D\)
のストリップに含まれる点を数えることと同じです。
つまり問題は、
平面上に幅 \(W\) の平行な 2 直線でできる帯を置き、その中に入る点の重み付き個数を最大化する
問題になります。
同じ座標に複数センサーがある場合、それらは常に同時に反応するため、座標ごとにまとめて「重み」として扱います。
素朴に「2 点を通る直線」をすべて試すだけでは不十分です。
例えば \(D=1\) で点が \((0,0)\), \((0,2)\) にある場合、最適なレーザー光線は \(y=1\) ですが、この直線はどちらの点も通りません。
そこで、レーザー光線そのものではなく、幅 \(W\) のストリップの境界線に注目します。
最適なストリップは、少し平行移動・回転しても含まれる点数が減らないように調整できるため、次のどちらかの形にできます。
- 片方の境界線上に 2 点以上ある
- 両方の境界線上にそれぞれ 1 点ずつある
したがって、この 2 種類の候補だけを列挙すれば十分です。
アルゴリズム
まず、同じ座標にあるセンサーをまとめます。
以降、各点 \(P_i=(X_i,Y_i)\) は重み \(w_i\) を持つものとして扱います。
1. \(D=0\) の場合
\(D=0\) のとき、ストリップの幅は \(0\) なので、単に同一直線上にある点の重みの最大値を求めればよいです。
各点 \(P_i\) を基準にして、他の点への方向ベクトルを正規化します。
方向ベクトル \((dx,dy)\) に対して、
\(g=\gcd(|dx|,|dy|)\)
で割り、
\((dx/g,dy/g)\)
を使います。
ただし、反対向きは同じ直線なので、符号を統一します。
各方向ごとに重みを合計し、最大値を更新します。
2. \(D>0\) の場合
幅を
\(W=2D\)
とします。
ケース A: 片方の境界線上に 2 点ある場合
点 \(P_i\), \(P_j\) が同じ境界線上にあるとします。
この境界線の方向ベクトルを
\((dx,dy)=P_j-P_i\)
とすると、その法線ベクトルは例えば
\((dy,-dx)\)
です。
法線ベクトルを \(n=(n_x,n_y)\) とします。
点 \(P_k\) について、
\(s=n_x(X_k-X_i)+n_y(Y_k-Y_i)\)
を考えます。
これは、点 \(P_k\) が境界線から法線方向にどれだけ離れているかを表す量です。
点 \(P_k\) がストリップ内に入る条件は、境界線の片側について
\(0 \leq s \leq W|n|\)
または反対側について
\(-W|n| \leq s \leq 0\)
です。
平方根を避けるため、実装では
\(s^2 \leq W^2(n_x^2+n_y^2)\)
で判定しています。
境界線の両側のどちらにストリップを置くかで個数が変わるので、両方数えて大きい方を使います。
ケース B: 両方の境界線上にそれぞれ 1 点ある場合
点 \(P_i\) が一方の境界線上、点 \(P_j\) がもう一方の境界線上にあるとします。
このとき、\(P_i\) から \(P_j\) へのベクトルを
\(v=(dx,dy)\)
とし、
\(r^2=dx^2+dy^2\)
とします。
2 点が幅 \(W\) のストリップの反対側の境界に乗るためには、少なくとも
\(r > W\)
である必要があります。
法線方向は、\(v\) への射影がちょうど \(W\) になる方向です。
これは、\(r>W\) のとき 2 通りあります。
\(v\) に垂直なベクトルを
\(q=(-dy,dx)\)
とすると、法線方向に比例するベクトルは
\(h_\pm = Wv \pm \sqrt{r^2-W^2}q\)
と表せます。
このベクトルは長さが \(r^2\) になるようにスケールされており、
\(h_\pm \cdot v = Wr^2\)
を満たします。
点 \(P_k\) について、\(u=P_k-P_i\) とすると、ストリップ内にある条件は
\(0 \leq h_\pm \cdot u \leq Wr^2\)
です。
実装では
\(h_\pm \cdot u = W(v\cdot u) \pm \sqrt{r^2-W^2}(q\cdot u)\)
を使って判定しています。
平方根が整数でない場合もあるため、浮動小数点数は使わず、平方して大小比較することで厳密に判定しています。
以上の 2 種類の候補をすべて試し、最大値を答えます。
計算量
重複をまとめた後の異なる座標数を \(M\) とします。
\(M \leq N\) です。
- 時間計算量: \(O(M^3)\)
- 空間計算量: \(O(M^2)\)
\(N \leq 200\) なので、\(O(N^3)\) で十分間に合います。
実装のポイント
同じ座標のセンサーは重みとしてまとめます。
\(D=0\) の場合は、最大共線点数を求める問題として別処理します。
距離判定では平方根や浮動小数点数を避け、整数演算で比較します。
ストリップの境界上の点も反応するため、不等号はすべて \(\leq\) を使います。
答えが \(N\) になった時点で、それ以上改善できないので早期終了できます。
ソースコード
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()
この解説は gpt-5.5-high によって生成されました。
posted:
last update: