Meeting on the Line
Contest: Codeforces Round 823 (Div. 2)
Difficulty rating: 1600
Tags: binary search, geometry, greedy, implementation, math, ternary search

$$$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.

Input format:
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$$$.

Output format:
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}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
- 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).

Example input:
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

Example output:
0
2
2.5
2
1
3
6

Editorial:
There are many solutions to this problem, here are 2 of them.
1) Let people be able to meet in time $$$T$$$, then they could meet in time $$$T + \varepsilon$$$, where $$$\varepsilon > 0$$$. So we can find $$$T$$$ by binary search. It remains to learn how to check whether people can meet for a specific time $$$T$$$. To do this, for the $$$i$$$-th person, find a segment of positions that he can get to in time $$$T$$$: if $$$T < t_i$$$ then this segment is empty, otherwise it is $$$[x_i - (T - t_i), x_i + (T - t_i)]$$$. Then people will be able to meet only if these segments intersect, that is, the minimum of the right borders is greater than or equal to the maximum of the left borders. In order to find the answer by the minimum $$$T$$$, you need to intersect these segments in the same way (should get a point, but due to accuracy, most likely, a segment of a very small length will turn out) and take any point of this intersection. Asymptotics is $$$O(n \log n)$$$.
2) If all $$$t_i$$$ were equal to $$$0$$$, then this would be a classical problem, the solution of which would be to find the average of the minimum and maximum coordinates of people. We can reduce our problem to this one if we replace the person ($$$x_i$$$, $$$t_i$$$) with two people: ($$$x_i - t_i$$$, $$$0$$$) and ($$$x_i + t_i$$$, $$$0$$$). Proof. Let the meeting be at the point $$$y$$$. Let $$$x_i \le y$$$. Then this person will need $$$t_i + y - x_i$$$ of time to get to her, and the two we want to replace him with — $$$y - x_i + t_i$$$ and $$$y - x_i - t_i$$$. it is easy to see that the first value is equal to the initial value, and the second is not greater than the initial value, then the maximum of these two values is equal to the initial value. The proof is similar for the case $$$y \le x_i$$$. Then for any meeting point, the time in the original problem and after the replacement does not differ, which means that such a replacement will not change the answer and it can be done. Asymptotics is $$$O(n)$$$.