E - Closest Moment 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 450

問題文

高橋君と青木君が二次元平面上を歩きます。

高橋君のスタート地点は (TS_X, TS_Y)、ゴール地点は (TG_X, TG_Y) です。 青木君のスタート地点は (AS_X, AS_Y)、ゴール地点は (AG_X, AG_Y) です。

二人は同時に各々のスタート地点を出発し、各々のゴール地点に向かって真っ直ぐ速さ 1 で歩き続け、各々のゴール地点に到達すると停止します。 (出発は同時ですが、停止するタイミングは同時とは限らないことに注意してください。)

二人の間の距離が最も短いタイミング(二人が出発する瞬間および停止した後を含む)における、二人の間の距離を求めてください。

ここで、距離はユークリッド距離を指すものとします。すなわち、2(x_1,y_1),(x_2,y_2) の間の距離は \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} として定められます。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\leq T\leq 2\times 10^5
  • -100\leq TS_X,TS_Y,TG_X,TG_Y,AS_X,AS_Y,AG_X,AG_Y \leq 100
  • (TS_X,TS_Y)\neq (TG_X,TG_Y)
  • (AS_X,AS_Y)\neq (AG_X,AG_Y)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

\text{case}_ii 番目のテストケースを表す。各テストケースは以下の形式で与えられる。

TS_X TS_Y TG_X TG_Y
AS_X AS_Y AG_X AG_Y

出力

T 行出力せよ。i 行目 (1\leq i\leq T) には i 番目のテストケースに対する答えを出力せよ。

出力は、真の値との絶対誤差または相対誤差が 10^{-6} 以下のとき、正解と判定される。


入力例 1

4
0 0 -2 2
-1 -1 4 4
4 0 2 0
6 0 8 0
1 0 1 1
-1 0 1 1
-8 9 2 6
-10 -10 17 20

出力例 1

1.000000000000000
2.000000000000000
0.000000000000000
1.783905950993199

1 番目のテストケースについて、二人が出発する時刻を 0 とおくと、二人の行動は以下のようになります。

  • 時刻 0:高橋君が (0,0) を出発し、(-2,2) に向かって速さ 1 で歩き始める。同時に、青木君が (-1,-1) を出発し、(4,4) に向かって速さ 1 で歩き始める。
  • 時刻 2\sqrt{2}:高橋君がゴール地点の (-2,2) に到達し、停止する。このとき、青木君は (1,1) におり、まだ歩き続けている。
  • 時刻 5\sqrt{2}:青木君がゴール地点の (4,4) に到達し、停止する。

二人の間の距離が最も短いのは時刻 \frac{1}{\sqrt{2}} であり、このとき高橋君と青木君はそれぞれ (-\frac{1}{2},\frac{1}{2}), (-\frac{1}{2},-\frac{1}{2}) にいて、その距離は 1 です。

2 番目のテストケースについて、二人の間の距離が最も短いのは二人が出発する瞬間であり、そのときの距離は 2 です。

3 番目のテストケースについて、二人の間の距離が最も短いのは二人が共に停止した後であり、そのときの距離は 0 です。

Score : 450 points

Problem Statement

Takahashi and Aoki walk on a two-dimensional plane.

Takahashi's start point is (TS_X, TS_Y) and goal point is (TG_X, TG_Y). Aoki's start point is (AS_X, AS_Y) and goal point is (AG_X, AG_Y).

They simultaneously depart from their respective start points and walk straight toward their respective goal points at speed 1, and stop when they reach their respective goal points. (Note that they depart simultaneously, but they do not necessarily stop at the same time.)

Find the distance between them at the moment when the distance between them is shortest (including the moment they depart and after they stop).

Here, distance refers to Euclidean distance. That is, the distance between two points (x_1,y_1),(x_2,y_2) is defined as \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}.

You are given T test cases, so solve each of them.

Constraints

  • 1\leq T\leq 2\times 10^5
  • -100\leq TS_X,TS_Y,TG_X,TG_Y,AS_X,AS_Y,AG_X,AG_Y \leq 100
  • (TS_X,TS_Y)\neq (TG_X,TG_Y)
  • (AS_X,AS_Y)\neq (AG_X,AG_Y)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

\text{case}_i represents the i-th test case. Each test case is given in the following format:

TS_X TS_Y TG_X TG_Y
AS_X AS_Y AG_X AG_Y

Output

Output T lines. The i-th line (1\leq i\leq T) should contain the answer for the i-th test case.

Your answer will be considered correct if the absolute or relative error from the true value is at most 10^{-6}.


Sample Input 1

4
0 0 -2 2
-1 -1 4 4
4 0 2 0
6 0 8 0
1 0 1 1
-1 0 1 1
-8 9 2 6
-10 -10 17 20

Sample Output 1

1.000000000000000
2.000000000000000
0.000000000000000
1.783905950993199

For the first test case, let time 0 be the moment they depart. Their behavior is as follows:

  • Time 0: Takahashi departs from (0,0) and starts walking toward (-2,2) at speed 1. At the same time, Aoki departs from (-1,-1) and starts walking toward (4,4) at speed 1.
  • Time 2\sqrt{2}: Takahashi reaches his goal point (-2,2) and stops. At this time, Aoki is at (1,1) and is still walking.
  • Time 5\sqrt{2}: Aoki reaches his goal point (4,4) and stops.

The distance between them is shortest at time \frac{1}{\sqrt{2}}, when Takahashi and Aoki are at (-\frac{1}{2},\frac{1}{2}) and (-\frac{1}{2},-\frac{1}{2}) respectively, and the distance is 1.

For the second test case, the distance between them is shortest at the moment they depart, and the distance at that time is 2.

For the third test case, the distance between them is shortest after they both stop, and the distance at that time is 0.