Day 24: Never Tell Me The Odds
Part One
给定起点和运动的向量，求哪些轨迹会相交在指定范围内
19, 13, 30 @ -2, 1, -2
18, 19, 22 @ -1, -1, -2
20, 25, 34 @ -2, -2, -4
假设点A(ax, ay)， B(bx, by)，它们对应的速度向量分别为(av, aw)，(bv, bw)，则A点在at时间后的坐标，与B点在bt时间后的坐标相同，则通过一元二次方程可以求解。
列出方程
ax + av * at = bx + bv * bt
ay + aw * at = by + bw * bt
过滤掉完全平行的轨迹，且at和bt时间需为正数。完整的SQL如下
WITH RECURSIVE origin AS (
SELECT _row, split_part(position, ', ', 1) :: bigint as x, split_part(position, ', ', 2) :: bigint as y,
split_part(velocity, ', ', 1) :: bigint as v, split_part(velocity, ', ', 2) :: bigint as w
FROM (
SELECT row_number() over () as _row, split_part(line, ' @ ', 1) as position, split_part(line, ' @ ', 2) as velocity
FROM lance_input
)t
)
SELECT a_row, b_row, ax + av * at as pos_x, ay + aw * at as pos_y
FROM (
SELECT (b.x * b.w - b.y * b.v + a.y * b.v - a.x * b.w) / (a.v * b.w - a.w * b.v) :: decimal as at,
(b.x * a.w - b.y * a.v + a.y * a.v - a.x * a.w) / (a.v * b.w - a.w * b.v) :: decimal as bt,
a.x as ax, a.y as ay, a.v as av, a.w as aw, a._row as a_row, b._row as b_row
FROM origin a
JOIN origin b
on a._row < b._row
AND a.v * b.w != a.w * b.v
) t
WHERE at >= 0 and bt >= 0
AND (ax + av * at) between 200000000000000 and 400000000000000
AND (ay + aw * at) between 200000000000000 and 400000000000000
Part Two
计算从某个起点出发的某个速度的射线，可以恰好与所有的冰雹相碰撞
假定不考虑z轴，起点为(x, y)，速度为(v, w)。与其中两个点A(ax, ay)和B(bx, by)相撞，那么可以得出
列出方程
x + v * at = ax + av * at
=> at = (ax - x) / (v - av)
y + w * at = ay + aw * at
=> at = (ay - y) / (w - aw)
=> (ax - x) / (v - av) = (ay - y) / (w - aw)
=> (ax - x) * (w - aw) = (ay - y) * (v - av)
=> ax * w - ax * aw - x * w + x * aw = ay * v - ay * av - y * v + y * av
=> y * v - x * w = ay * v - ay * av + y * av - ax * w + ax * aw - x * aw
将A替换为B
y * v - x * w = by * v - by * bv + y * bv - bx * w + bx * bw - x * bw
=> ay * v - ay * av + y * av - ax * w + ax * aw - x * aw = by * v - by * bv + y * bv - bx * w + bx * bw - x * bw
=> (ay - by) * v + (av - bv) * y + (bx - ax) * w + (bw - aw) * x = ay * av - ax * aw - by * bv + bx * bw
接下来构建四个等式即可，通过wolframalpha计算出四个未知数
代入参数，计算出时间，从而构造出z和z方向上的速度u的方程
(229809969824403 - z) / (u - 106) = 516434301805
(226146987100003 - z) / (u - 158) = 215244678825