ABC426-E の解説に以下のような記述があります。
点と線分の距離は外積・内積等をうまく使って O(1) で求めることもできますが、本問題においては三分探索を用いても十分高速に動作します。
この「外積・内積等をうまく使う方法」について、本番でこの解法を使って通せて気分が良いので 公式解説はもちろんユーザー解説にも詳しい解説はないようなので、僭越ながら自主解説を書こうと思います。
原点と線分の最短距離
この問題のクエリで問われているのは、ある点と別のある点が同時に直線運動をするとき、その最短距離はいくらかということです。これは相対距離を考えることによって、ある線分と原点との距離 に帰着できます。
直線との距離
まず、問題を単純にするために、ある 直線 と原点との距離を考えます。
おなじみの点と直線の公式では、方程式 $ax+by+c=0$ の係数がわかっている場合は、
\frac{|a\cdot0+b\cdot0+c|}{\sqrt{a^2+b^2}} = \frac{|c|}{\sqrt{a^2+b^2}}
で求められますが、$2$ 点の座標からも求められます。
上の図を見ると三角形 $\Delta OPQ$ の面積は $PQ$ と垂線をかけて $2$ で割ったものと一致しています。 $\Delta OPQ$ の面積は $\vec{P}$ と $\vec{Q}$ の外積から求められます。（二次元平面上のベクトルの外積の大きさは、そのベクトルからなる平行四辺形と一致しています）
よって、もとめる距離 $d$ は、
\displaylines{
\frac{1}{2} d|\vec{PQ}| = \Delta OPQ \\
d|\vec{PQ}| = 2\Delta OPQ = |\vec{P} \times \vec{Q}| \\
d = \frac{|\vec{P} \times \vec{Q}|}{|\vec{PQ}|}
}
となります。
線分との距離
しかし、線分との距離になるともう少し複雑です。垂線が線分 $PQ$ を通らない場合は、垂線を最短距離とすることができません。このとき、最短距離は $OP$ か $OQ$ のどちらかになります。
垂線が線分に含まれるかどうか？ が一番の問題となります。
これを求めるために、ちょっと図を引き伸ばして以下のように見てみます。
$\vec{PO}$ のうち、$\vec{PQ}$ と平行な成分だけを抽出した場合、これが $PQ$ 内に収まっている場合は、点 $O'$ は線分 $PQ$ 内に収まっていると言えます。
\displaylines{
0<|\vec{PO'}| < |\vec{PQ}| \\
0<|\vec{PO}| \cos{\theta} < |\vec{PQ}| \\
0<|\vec{PO}||\vec{PQ}| \cos{\theta} < |\vec{PQ}|^2 \\
0<\vec{PO}\cdot\vec{PQ} < |\vec{PQ}|^2 \\
}
これが求める条件になります。
なお、
0<\frac{\vec{PO}\cdot\vec{PQ}}{|\vec{PQ}|^2}<1
と変形させた場合、この中身は $P \rightarrow Q$ の媒介変数 $t$ と一致します。（$t=0$ のとき $P$、$t=1$ のとき $Q$ に位置する）
- この条件を満たすときは、点と直線の最短距離が最短距離
- そうでないときは、どちらかの点との距離のうち、短いものが最短距離
となります。
実装
// インクルードや独自ライブラリは省略
double closest(Point p,Point q,Point o){
Point OP = p-o;
Point OQ = q-o;
Point PQ = q-p;
double t = (-OP*PQ);
if(0<t && t<PQ.norm()*PQ.norm()){
return abs(OP^OQ)/PQ.norm();
}else{
return min(OP.norm(),OQ.norm());
}
}
double solve(){
Point ts,tg,as,ag;
cin >> ts >> tg >> as >> ag;
Point rs = as-ts;
Point rg = ag-tg;
double t_dist = (tg-ts).norm();
double a_dist = (ag-as).norm();
double m_dist = min(t_dist,a_dist);
Point tm = ts + (tg-ts)*(m_dist/t_dist);
Point am = as + (ag-as)*(m_dist/a_dist);
Point rm = am-tm;
Point origin({0,0});
double ans = min(closest(rs,rm,origin),closest(rm,rg,origin));
return ans;
}
int main(){
int t;
cin >> t;
while(t--){
cout << fixed << setprecision(20) << solve() << endl;
}
}