【题目描述】

今人不见古时月，今月曾经照古人。

梦回长安，大唐风华，十里长安花，一日看尽。 

唐长安城是当时世界上规模最大、建筑最宏伟、规划布局最为规范化的一座都城。其营建 制度规划布局的特点是规模空前、创设皇城、三城层环、六坡利用、布局对称、街衢宽阔、坊 里齐整、形制划一、渠水纵横、绿荫蔽城、郊环祀坛。而所谓的十里长安街，位于长安城的中 轴线上，即唐长安城的朱雀大街，又称承天门大街。唐朝官员们住在各个“坊”里，上朝下朝 都需要通过朱雀大街。

为了保持各大家族的联系和友谊，各官员往往会每月办一次宴会。为了方便描述，我们把 朱雀大街看成一个数轴，各官员所居住的“坊”缩略为数轴上的一个坐标点。大家决定选一处 地点（该地点是数轴上的某一个点，不一定坐标点）办宴会。由于唐朝宵禁严格，大家又都希 望交流时间尽可能长，因此想要使宴会开始时间尽可能早。又因为大唐注重礼仪，因此，参加 宴会的官员会花一定时间盛装打扮过后才前往宴会地点（不一定是坐标点）。 更具体地，一条纵向的街道上（相当于一维坐标）有 n 个人居住，其中第i个人居住在xi （非负整数） 位置（坐标点）上。每月他们会选择在 x0（数轴上的某一个点，不一定坐标点） 出举办宴会。 已知第 i 个人从 xi 出发前往宴会地点 x0 处需要花费 |xi-x0| 的时间，另外，他还需要花费 ti的时间进行打扮，换言之，他共需要花费 |xi-x0| + ti 的时间到达宴会举办处。 假设初始时刻为 0 。

这 n 个人开始打扮和出发前往宴会处，他们想要使得宴会的开始时间 尽可能早，于是向你求助，请你帮助他们确定好最优的宴会举办地点 x0。 注：|xi-x0| 表示xi 与 x0 之差的绝对值，且题目中 n 个人的居住地点坐标均为整数。

【输入描述】

第一行一个正整数 T，表示测试数据的组数。 

接下来对于每组测试数据（注意：每组测试数据有 3 行数据，以下共 3*T 行数据）：

 第一行一个正整数 n，表示总官员人数。

 第二行共 n 个非负整数x1,x2,x3,...xn 分别表示这 n 个人在数轴上的坐标。

 第三行共 n 个非负整数t1,t2,t3...tn分别表示这 n 个人出发前的打扮时间

【输出描述】

共输出 T 行数据，对于每组测试数据，输出一行一个实数（如果是整数按整数输出，如果有 小数，保留 1 位小数输出），表示使宴会开始时间最早的最优举办地点坐标x0。（很显然，x0是唯一的）

【样例输入】

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

【样例说明】

初始时刻为 0。 对于第一组测试数据只有 1 个人，坐标为 0，打扮时间为 3，很显然 x0 就定在坐标 0 处，使 得宴会开始时间为 3 且最早。 

对于第二组测试数据有 2 个人，坐标分别为 3、1，打扮时间均为 0，很显然 x0 定在坐标 2 处，使得宴会开始时间为 1 且最早。 

对于第三组测试数据有 2 个人，坐标分别为 1、4，打扮时间均为 0，很显然 x0 定在坐标 2.5 处，使得宴会开始时间为 1.5 且最早。

【数据范围】

对于 30% 的数据,T=1，1<=n<=100, 0<=xi, ti<=1000;

对于 60% 的数据，T<=n<=10^4, 0<=xi, ti<=10^5； 

对于100%的数据，1<=T<=10^3, 1<=n<=10^5, 0<=xi, ti<=10^8,且保证所有测试数据的n加起来都不超过2*10^5

【题目分析】

• 这道题目是一道英文版原题 ：meeting on the line

• 跟这道题比较相近的是：仓库选址

• 我们把测试数据简单划分一下：

  
  

输入:
1
0
3
输出:
0

输入:
2
3 1
0 0
输出:
2

输入：
2
1 4
0 0
输出：
2.5

输入：
3
1 2 3
0 0 0
输出：
2

输入：
3
1 2 3
4 1 2
输出：
1

题目含义，在数轴上找一个点，使得宴会的开始时间尽可能早，就是使得 |xi - x0| +ti 距离最短。

我们把时间看成位置，这样的话xi+ti 或xi-ti就表示真实的位置了。

如果ti时间全部是0，那么肯定是最左侧的点和最右侧的点之间的中点。

如果ti不是0，那么需要找出最左侧的点和最右侧的点，我们要让时间最小，显然要让靠左的点尽可能向右走，靠右的点尽可能往左走。那么我们遍历所有点，对于每个人或者点，算出在他准备走的这段时间内，向右走的最远距离，在所有人中取最小值。向左走的最远位置，在所有人中取最大值。这两个数分别为最左和最右，取中点即可。

• 输出的时候要特别注意一下，用printf。

【参考代码】

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N=100010;
int t,n,l=1e8,r=-1e8;
int x[N],ti[N];
int main() {
    scanf("%d",&t);
    while(t--) {
        memset(x,0,sizeof(x));
        memset(ti,0,sizeof(ti));
        l=1e8;
        r=-1e8;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%d",&x[i]);
        for(int i=1; i<=n; i++)
            scanf("%d",&ti[i]);
        for(int i=1; i<=n; i++) {
            int u=x[i]-ti[i];//打扮时间等于左移
            int v=x[i]+ti[i];//打扮时间等于右移
            l=min(l,u);
            r=max(r,v);
        }
        //printf("l=%d,r=%d\n",l,r);
        if((l+r)%2==0) printf("%d\n",(r+l)/2);
        else printf("%.1lf\n",1.0*(r+l)/2);
    }
    return 0;
}