CF1730B.Meeting on the Line

$n$ people live on the coordinate line, the $i$-th one lives at the point $x_i$ ($1 \le i \le n$). They want to choose a position $x_0$ to meet. The $i$-th person will spend $|x_i - x_0|$ minutes to get to the meeting place. Also, the $i$-th person needs $t_i$ minutes to get dressed, so in total he or she needs $t_i + |x_i - x_0|$ minutes.

Here $|y|$ denotes the absolute value of $y$.

These people ask you to find a position $x_0$ that minimizes the time in which all $n$ people can gather at the meeting place.

有 $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$ 个人均能到达集会地点所需的时间（即所有人中最大耗时）最小化。

The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases. Then the test cases follow.

Each test case consists of three lines.

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of people.

The second line contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^{8}$) — the positions of the people.

The third line contains $n$ integers $t_1, t_2, \dots, t_n$ ($0 \le t_i \le 10^{8}$), where $t_i$ is the time $i$-th person needs to get dressed.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print a single real number — the optimum position $x_0$. It can be shown that the optimal position $x_0$ is unique.

Your answer will be considered correct if its absolute or relative error does not exceed $10^{−6}$. Formally, let your answer be $a$, the jury's answer be $b$. Your answer will be considered correct if $\frac{|a−b|}{max(1,|b|)} \le 10^{−6}$.

对于每个测试用例，输出一个实数——最优位置 $x_0$。可以证明最优位置 $x_0$ 是唯一的。

若你的答案的绝对误差或相对误差不超过 $10^{−6}$，则视为正确。形式化地，设你的答案为 $a$，评测组的答案为 $b$，当且仅当 $\frac{|a−b|}{\max(1,|b|)} \le 10^{−6}$ 时，你的答案被视为正确。

• In the $1$-st test case there is one person, so it is efficient to choose his or her position for the meeting place. Then he or she will get to it in $3$ minutes, that he or she need to get dressed.

• In the $2$-nd test case there are $2$ people who don't need time to get dressed. Each of them needs one minute to get to position $2$.

• In the $5$-th test case the $1$-st person needs $4$ minutes to get to position $1$ ($4$ minutes to get dressed and $0$ minutes on the way); the $2$-nd person needs $2$ minutes to get to position $1$ ($1$ minute to get dressed and $1$ minute on the way); the $3$-rd person needs $4$ minutes to get to position $1$ ($2$ minutes to get dressed and $2$ minutes on the way).

• 在第 $1$ 个测试用例中，只有一个人，因此选择他或她的位置作为会议地点是最优的。此时，他或她需要 $3$ 分钟到达该地点（全部用于穿衣）。

• 在第 $2$ 个测试用例中，有 $2$ 个人，他们均无需穿衣时间。每人到达位置 $2$ 均需 $1$ 分钟。

• 在第 $5$ 个测试用例中，第 $1$ 个人到达位置 $1$ 需要 $4$ 分钟（其中 $4$ 分钟用于穿衣，路上耗时 $0$ 分钟）；第 $2$ 个人到达位置 $1$ 需要 $2$ 分钟（其中 $1$ 分钟用于穿衣，路上耗时 $1$ 分钟）；第 $3$ 个人到达位置 $1$ 需要 $4$ 分钟（其中 $2$ 分钟用于穿衣，路上耗时 $2$ 分钟）。