#P1730B. Meeting on the Line

    ID: 7900 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchgeometrygreedyimplementationmathternary search*1600

Meeting on the Line

Description

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

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

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

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

Samples

<div class="test-example-line test-example-line-even test-example-line-0">7</div><div class="test-example-line test-example-line-odd test-example-line-1">1</div><div class="test-example-line test-example-line-odd test-example-line-1">0</div><div class="test-example-line test-example-line-odd test-example-line-1">3</div><div class="test-example-line test-example-line-even test-example-line-2">2</div><div class="test-example-line test-example-line-even test-example-line-2">3 1</div><div class="test-example-line test-example-line-even test-example-line-2">0 0</div><div class="test-example-line test-example-line-odd test-example-line-3">2</div><div class="test-example-line test-example-line-odd test-example-line-3">1 4</div><div class="test-example-line test-example-line-odd test-example-line-3">0 0</div><div class="test-example-line test-example-line-even test-example-line-4">3</div><div class="test-example-line test-example-line-even test-example-line-4">1 2 3</div><div class="test-example-line test-example-line-even test-example-line-4">0 0 0</div><div class="test-example-line test-example-line-odd test-example-line-5">3</div><div class="test-example-line test-example-line-odd test-example-line-5">1 2 3</div><div class="test-example-line test-example-line-odd test-example-line-5">4 1 2</div><div class="test-example-line test-example-line-even test-example-line-6">3</div><div class="test-example-line test-example-line-even test-example-line-6">3 3 3</div><div class="test-example-line test-example-line-even test-example-line-6">5 3 3</div><div class="test-example-line test-example-line-odd test-example-line-7">6</div><div class="test-example-line test-example-line-odd test-example-line-7">5 4 7 2 10 4</div><div class="test-example-line test-example-line-odd test-example-line-7">3 2 5 1 4 6</div>
0
2
2.5
2
1
3
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).