$$$n$$$ 人生活在坐标线上,第 $$$i$$$ 人生活在点 $$$x_i$$$ ($$$1 \le i \le n$$$)。他们想要选择一个位置 $$$x_0$$$ 来见面。第 $$$i$$$ 人将花费 $$$|x_i - x_0|$$$ 分钟到达集合地点。此外,第 $$$i$$$ 人需要 $$$t_i$$$ 分钟穿衣服,因此他或她总共需要 $$$t_i + |x_i - x_0|$$$ 分钟。
这里$$$|y|$$$表示$$$y$$$的绝对值。
这些人要求你找到一个位置 $$$x_0$$$,以尽量减少所有 $$$n$$$ 人聚集在集合地点的时间。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。然后是测试用例。
每个测试用例由三行组成。
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 人数。
第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le 10^{8}$$$) — 人员的位置。
第三行包含 $$$n$$$ 整数 $$$t_1, t_2, \dots, t_n$$$ ($$$0 \le t_i \le 10^{8}$$$),其中 $$$t_i$$$ 是第 $$$i$$$ 人需要穿衣服的时间。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个实数 - 最佳位置 $$$x_0$$$。可以证明最优位置$$$x_0$$$是唯一的。
如果您的答案的绝对或相对误差不超过 $$$10^{−6}$$$,则视为正确。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{|a−b|}{max(1,|b|)} \le 10^{−6}$$$,您的答案将被视为正确。
示例
输入 #1
7 1 0 3 2 3 1 0 0 2 1 4 0 0 3 1 2 3 0 0 0 3 1 2 3 4 1 2 3 3 3 3 5 3 3 6 5 4 7 2 10 4 3 2 5 1 4 6
输出 #1
0 2 2.5 2 1 3 6
注意
- 在 $$$1$$$-st 测试用例中只有一个人,因此选择他或她的会议地点位置是有效的。然后他或她将在 $$$3$$$ 分钟内完成,他或她需要穿好衣服。
- 在 $$$2$$$-nd 测试用例中,有 $$$2$$$ 人不需要时间穿衣服。他们每个人都需要一分钟才能到达 $$$2$$$ 位置。
- 在第 $$$5$$$ 测试用例中,第 $$$1$$$ 人需要 $$$4$$$ 分钟才能到达 $$$1$$$ 位置($$$4$$$ 分钟穿好衣服,$$$0$$$ 分钟在路上); $$$2$$$-nd 人需要 $$$2$$$ 分钟到达位置 $$$1$$$($$$1$$$ 分钟穿好衣服,$$$1$$$ 分钟在路上);第 $$$3$$$ 人需要 $$$4$$$ 分钟才能到达 $$$1$$$ 位置($$$2$$$ 分钟穿好衣服,$$$2$$$ 分钟在路上)。