A15270. 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.
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$ .
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}$ .
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}$ .
输入输出样例
输入 #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
说明/提示
- 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).
- 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).