← 返回题目列表

AtCoder · abc426_e

H. 最近的时刻

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

高桥和青木行走在二维平面上。

高桥的起点是 (TS_X, TS_Y) 目标点是 (TG_X, TG_Y)。 青木的出发点是 (AS_X, AS_Y) 目标点是 (AG_X, AG_Y).

他们同时从各自的起点出发,高速直奔各自的目标点 1,并在达到各自的目标点时停止。 (请注意,它们同时出发,但不一定同时停止。)

求他们之间距离最短时刻(包括他们出发时和停止后)之间的距离。

这里,距离是指欧几里得距离。也就是两点之间的距离 (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}_i 代表 i- 第一个测试用例。每个测试用例均按以下格式给出:

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

对于第一个测试用例,让时间 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.

对于第三个测试用例,他们都停止后,他们之间的距离最短,此时的距离为 0.