CF51C Three Base Stations

新 Vasjuki 村沿高速公路延伸，因此村中每座房屋都可以用其相对于某一固定点的偏移量（即 $x_{i}$ 坐标）来表示。这个村庄共有 $n$ 座房屋，第 $i$ 座房屋位于坐标 $x_{i}$ 处。 TELE3 是一家移动通信服务提供商，计划在村庄内设置三座基站，以确保村中每座房屋都能接收到移动信号。一个功率为 $d$、位于 $t$ 处的基站可以为坐标区间 $[t-d, t+d]$（包括端点）上的所有房屋提供信号覆盖。 为简化工程（并防止混淆），三座基站的功率 $d$ 必须相同。请你求出能保证村庄内所有房屋都被信号覆盖所需的最小功率 $d$。

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^{5}$），表示村庄中的房屋数量。第二行包含 $n$ 个整数 $x_{1}, x_{2}, \ldots, x_{n}$（$1 \leq x_{i} \leq 10^{9}$），分别表示每座房屋的坐标。可能有两个或更多的房屋位于同一位置。房屋的坐标顺序是任意的。

输出所需的最小功率 $d$。第二行输出可供选择的三座基站的位置。每个坐标需保留 $6$ 位小数。基站可以布置在区间 $0$ 到 $2 \cdot 10^{9}$ 之间的任意位置。允许基站位置重复。如果有多解，请输出任意一个。

由 ChatGPT 5 翻译