← 返回题目列表

Codeforces · 51/C

C. 三个基站

中文机器翻译题面 查看原题

新 Vasjuki 村沿着高速公路延伸,这就是为什么村里的每栋房子都有相对于某个固定点(xi 坐标)的偏移的原因。该村庄由 n 栋房屋组成,第 i 栋房屋位于坐标为 xi 的点。

蜂窝通信提供商TELE3计划部署三个基站,为村里的每户家庭提供蜂窝通信。位于t点、功率为d的基站向段[t-d,t+d](包括边界)上的所有房屋提供通信。

为了简化集成(并且只是为了不混淆任何东西),所有三个站都计划拥有相同的 d 功率。 d 的最小值足以为村里的所有房屋提供蜂窝通信。

输入

第一行包含一个整数n (1 ≤ n ≤ 2·105),代表村里的房屋数量。第二行包含房屋的坐标 - 整数序列 x1, x2, ..., xn (1 ≤ xi ≤ 109)。两座或多座房屋可能位于一个点上。坐标以任意顺序给出。

输出

打印所需的最小功率 d.在第二行中打印三个数字——基站位置的可能坐标。打印小数点后 6 位的坐标。站点的位置可以是从 0 到 2·109 之间的任意位置(包含 0 和 2·109)。基站具有匹配的坐标是可以接受的。如果有很多解决方案,请打印其中任何一个。

示例

输入 #1

4
1 2 3 4

输出 #1

0.500000
1.500000 2.500000 3.500000

输入 #2

3
10 20 30

输出 #2

0
10.000000 20.000000 30.000000

输入 #3

5
10003 10004 10001 10002 1

输出 #3

0.500000
1.000000 10001.500000 10003.500000