600107 - 信号覆盖

有一排m个办公室，其坐标为1、2、3……m的整数位置，其中n个人在这些办公室办公时需要进行WIFI信号覆盖。现在必须只安装x个相同规格的无线路由器，来完成WIFI信号覆盖。

相同规格是指其覆盖范围d相同。例如将一个路由器放在p坐标，则它覆盖的范围为[p-d,p+d]。

将办公室看做一个点，若路由器放在这个点上或这个点在WINFI信号覆盖范围内（含端点），则覆盖了这个办公室。求出在x==3时最小的d和每个路由器的位置p_i。

第一行，一个整数n，表示需要WIFI的人的个数。

接下来n行，每行一个整数p_i，表示第i人的办公室的位置。注意，办公室可能有多个人，他们的坐标将相同。

对于100%的数据：

1 \le n \le 2×10^5；

1 \le p_i \le 2×10^9。

一行，一个数字d_{min}，表示路由器的最小覆盖范围。

变量较多的问题往往需要多重循环（逐个迭代可能的每个变量，最终试出结果），通过将最内侧的循环变为check（检测函数）来缩短耗时。

但本题数据量非常大，观察题目所求：最小值，属于已知解区间：所有人中最小坐标和最大坐标之间，求确切值的问题。可以采用二分法进行查找d值：当通过check（检测函数）时，尝试向小的方向查找；当不通过时，尝试向大的方向查找。直到d的精度满足题目要求（小数点后6位，计算时计算到7位）。

进一步的，在check函数中使用二分法，可以进一步缩短耗时。