ベクトルの基本知識を前提とします。

この問題では、高橋君と青木君は常に一定の速度で直線運動をしています。直線運動において、ある点が位置 \(\bm{s_0}\) から出発して、一定の速度 \(\bm{v}\) で移動する場合、時刻 \(t\geq0\) におけるその点の位置は \(\bm{s}(t)=\bm{s_0}+t\bm{v}\) となります。

スタート地点とゴール地点 \(\text{TS}, \text{TG}, \text{AS}, \text{AG}\) を \(2\) 次元ベクトルとして扱います。高橋君が歩くのに要する総時間を \(t_\text{T}=|\text{TG}-\text{TS}|\) として、高橋君の速度ベクトルを \(\bm{v}_\text{T}=\frac1{t_\text{T}}(\text{TG}-\text{TS})\) として定義します。同様に、\(t_\text{A}\) を青木君が歩く総時間、\(\bm{v}_\text{A}\) を青木君の速度ベクトルとして定義します。

時刻 \(t\in[0, t_\text{T}]\) における高橋君の位置ベクトル \(\bm{s}_\text{T}(t)\) は、次のベクトル方程式によって与えられます。

\[\bm{s}_\text{T}(t)=\text{TS}+t\bm{v}_\text{T}\]

同様に、時刻 \(t\in[0, t_\text{A}]\) における青木君の位置ベクトル \(\bm{s}_\text{A}(t)\) は、次のように与えられます。

\[\bm{s}_\text{A}(t)=\text{AS}+t\bm{v}_\text{A}\]

---

対称性により、\(t_\text{T}\gt t_\text{A}\) の場合、高橋君と青木君の役割を入れ替え、\(t_\text{T}\leq t_\text{A}\) と仮定することができます。

高橋君と青木君は必ずしも同時に止まるわけではありません。そのため、元の問題を \(2\) つの場合に分けて考えます。

• \(t\in[0, t_\text{T}]\) の場合。すなわち、高橋君と青木君は各々のゴール地点に向かって歩き続ける場合。
• \(t\in(t_\text{T}, t_\text{A}]\) の場合。すなわち、高橋君が静止して、青木君が自分のゴール地点に向かって歩き続ける場合。

もし \(t_\text{T}=t_\text{A}\) であれば、\(2\) つ目の場合を考慮する必要がないため、答えは\(1\) つ目の場合における最短距離となります。\(t_\text{T}\lt t_\text{A}\) であれば、答えは \(2\) つの場合のうちの最短距離となります。

---

\(t\in[0, t_\text{T}]\) の場合を考えます。高橋君の視点からすると、青木君の相対的なスタート地点は \((\text{AS}-\text{TS})\) であり、相対速度は \((\bm{v}_\text{A}-\bm{v}_\text{T})\) となります。したがって、青木君の相対位置は

\[\bm{s}_\text{A}(t)-\bm{s}_\text{T}(t)=(\text{AS}-\text{TS})+t(\bm{v}_\text{A}-\bm{v}_\text{T})\]

で与えられます。この式は直線運動を表しているため、時刻 \(t\in[0, t_\text{T}]\) において、青木君の相対的な動きを線分として扱うことができます。

次に \(t\in(t_\text{T}, t_\text{A}]\) の場合を考えます。高橋君はゴール地点 \(\text{TG}\) に留まっているため、静止点 \(\text{TG}\) の視点から青木君の動きを考えると、青木君の相対的なスタート地点は \((\text{AS}-\text{TG})\) であり、相対速度は \(\bm{v}_\text{A}\) となります。したがって、青木君の相対位置は

\[\bm{s}_\text{A}(t)-\text{TG}=(\text{AS}-\text{TG})+t\bm{v}_\text{A}\]

で与えられます。この式も同様に直線運動を表しているため、時刻 \(t\in(t_\text{T}, t_\text{A}]\) においても、青木君の相対的な動きを線分として扱うことができます。

以上より、どちらの場合でも、元の問題は「与えられた線分と原点の最短距離を求める問題」に帰着されます。

---

以下の問題を考えます。

異なる端点 \(\bm{p}=(x_p, y_p)\) および \(\bm{q}=(x_q, y_q)\) で与えられる線分があります。この線分と原点の最短距離を求めてください。

この線分はベクトル方程式

\[L(\lambda)=\bm{p}+\lambda(\bm{q}-\bm{p})\]

で表すことができます。この式により、パラメータ \(\lambda\in[0, 1]\) に対する線分上の点が得られます。

ある点 \(L(\lambda)\) と原点の距離は

\[|L(\lambda)|=\sqrt{(x_p+\lambda(x_q-x_p))^2+(y_p+\lambda(y_q-y_p))^2}\]

となります。

\(|L(\lambda)|\) を最小化する \(\lambda\) は等式 \(\frac{\text{d}}{\text{d}\lambda}|L(\lambda)|=0\) の解で与えられますが、微分式がやや複雑です。そこで、\(|L(\lambda)|^2\) が最小値であるような \(\lambda\) について \(|L(\lambda)|\) も最小値となるという事実を用いて、代わりに \(\frac{\text{d}}{\text{d}\lambda}|L(\lambda)|^2=0\) を解くことにします。微分を計算すると

\[ \begin{aligned} \frac{\text{d}}{\text{d}\lambda}|L(\lambda)|^2&=\frac{\text{d}}{\text{d}\lambda}\left((x_p+\lambda(x_q-x_p))^2+(y_p+\lambda(y_q-y_p))^2\right)\\ &=2(x_q-x_p)(x_p+\lambda(x_q-x_p))+2(y_q-y_p)(y_p+\lambda(y_q-y_p))\\ &=0 \end{aligned} \]

となり、次の解が得られます。

\[\lambda=-\frac{x_p(x_q-x_p)+y_p(y_q-y_p)}{(x_q-x_p)^2+(y_q-y_p)^2}=-\frac{\bm{p}\cdot(\bm{q}-\bm{p})}{|\bm{q}-\bm{p}|^2}=\frac{\bm{p}\cdot(\bm{p}-\bm{q})}{|\bm{p}-\bm{q}|^2}\]

なお、上記の解は区間 \([0, 1]\) に含まれない場合もあります。解が \(0\) より小さい場合、原点に最も近い線分上の点は \(L(0)=\bm{p}\) となります。解が \(1\) より大きい場合、最も近い点は \(L(1)=\bm{q}\) となります。

---

よって、元の問題の最短距離を求めることができます。時間計算量は \(O(1)\) です。

実装例 (Python)