Background

Due to the pandemic, Shandong Province canceled the CSP-J 2022 certification event, and in March of the following year it set new problems and held a make-up contest within the province.

Problem Description

People today do not see the moon of ancient times, yet today’s moon once shone on people of old. Dreaming back to Chang’an, the grandeur of the Tang Dynasty, ten miles of Chang’an flowers, all seen in a single day.

Tang Chang’an was the largest city in the world at that time, with the most magnificent buildings and the most standardized planning layout. The characteristics of its construction system and planning layout included an unprecedented scale, the creation of the Imperial City, three-layer ring structure, use of six slopes, symmetrical layout, wide streets, neatly arranged wards, uniform design, crisscrossing canals, trees shading the city, and suburban ritual altars. The so-called Ten-mile Chang’an Street lay on the central axis of Chang’an, namely the Zhuque Avenue of Tang Chang’an, also known as Chengtianmen Avenue. Officials of the Tang Dynasty lived in various “wards”, and they had to pass through Zhuque Avenue when going to and returning from court.

To maintain connections and friendship among major families, officials would often hold a banquet once a month. For convenience, we view Zhuque Avenue as a number line, and each official’s ward is simplified to a coordinate point on the number line. They decide to choose a location (a point on the number line, not necessarily one of the coordinate points) to hold the banquet. Since the Tang Dynasty had strict curfews and everyone wanted the communication time to be as long as possible, they want the banquet to start as early as possible. Also, because the Tang Dynasty valued etiquette, each official will spend some time dressing up before going to the banquet location (also not necessarily a coordinate point).

More specifically, on a vertical street (equivalent to a one-dimensional coordinate), there are $n$ people living. Person $i$ lives at position $x_{i}$ (a non-negative integer) on the number line (a coordinate point). Every month they will choose to hold the banquet at $x_{0}$ (a point on the number line, not necessarily a coordinate point).

It is known that person $i$ needs $\left|x_{i}-x_{0}\right|$ time to travel from $x_{i}$ to the banquet location $x_{0}$. In addition, they need $t_{i}$ time to dress up. In other words, they need a total time of $\left|x_{i}-x_{0}\right|+t_{i}$ to arrive at the banquet location.

Assume the initial time is $0$. These $n$ people start dressing up and then set off for the banquet. They want the banquet to start as early as possible, so they ask for your help. Please help them determine the optimal banquet location $x_{0}$.

Note: $\left|x_{i}-x_{0}\right|$ denotes the absolute value of the difference between $x_{i}$ and $x_{0}$, and the home coordinates of the $n$ people in this problem are all integers.

Input Format

The first line contains a positive integer $T$, indicating the number of testdata groups.

Then for each group of testdata (note: each group has $3$ lines of data, for a total of $3\times T$ lines below):

The first line contains a positive integer $n$, indicating the total number of officials.

The second line contains $n$ non-negative integers $x_{1},x_{2},\dots,x_{n}$, representing the coordinates of these $n$ people on the number line.

The third line contains $n$ non-negative integers $t_{1},t_{2},\dots,t_{n}$, representing the dressing-up time before departure for each person.

Output Format

Output $T$ lines in total. For each group of testdata, output one line with a real number (if it is an integer, output it as an integer; if it has decimals, output it with $1$ decimal place), representing the optimal location coordinate $x_{0}$ that makes the banquet start time as early as possible. (Clearly, $x_{0}$ is unique.)

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

0
2
2.5
2
1
3
6

Hint

Sample Explanation

The initial time is $0$.

For the first group of testdata, there is only $1$ person, with coordinate $0$ and dressing-up time $3$. Obviously, $x_{0}$ should be set at coordinate $0$, making the banquet start time $3$, which is the earliest.

For the second group of testdata, there are $2$ people with coordinates $3$ and $1$, and both have dressing-up time $0$. Obviously, $x_{0}$ should be set at coordinate $2$, making the banquet start time $1$, which is the earliest.

For the third group of testdata, there are $2$ people with coordinates $1$ and $4$, and both have dressing-up time $0$. Obviously, $x_{0}$ should be set at coordinate $2.5$, making the banquet start time $1.5$, which is the earliest.

Constraints

For $30\%$ of the data, $T=1,n\le100,0\le x_{i},t_{i}\le1000$.

For $60\%$ of the data, $n\le10^{4},0\le x_{i},t_{i}\le10^{5}$.

For $100\%$ of the data, $1\le T\le10^{3},n\le10^{5},0\le x_{i},t_{i}\le10^{8}$, and it is guaranteed that the sum of $n$ over all testdata does not exceed $2\times10^{5}$.

Translated by ChatGPT 5