Meeting on the Line (Codeforces 1730B)
Tags: Greedy, 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: 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: 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}$$$.

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

Sample Inputs:
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

Sample Outputs:
0
2
2.5
2
1
3
6

Solution (Python):
tc = int(input())
for i in range(1, tc + 1):
    n = int(input())
    x = list(map(int, input().split()))
    t = list(map(int, input().split()))
    a = [i + j for (i, j) in zip(x, t)]
    b = [i - j for (i, j) in zip(x, t)]
    ans = (max(a) + min(b)) / 2
    print(ans)

Solution (Python):
tc = int(input())
for i in range(1, tc + 1):
    n = int(input())
    x = list(map(int, input().split()))
    t = list(map(int, input().split()))
    a = [i + j for (i, j) in zip(x, t)]
    b = [i - j for (i, j) in zip(x, t)]
    ans = (max(a) + min(b)) / 2
    print(ans)

Solution (Python):
I = lambda : [*map(int, input().split())]
rr = range
for _ in rr(I()[0]):
    (n,) = I()
    po = I()
    ti = I()
    a = [x - y for (x, y) in zip(po, ti)]
    a += [x + y for (x, y) in zip(po, ti)]
    print((min(a) + max(a)) / 2)