CF51C.Three Base Stations
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The New Vasjuki village is stretched along the motorway and that's why every house on it is characterized by its shift relative to some fixed point — the xi coordinate. The village consists of n houses, the i -th house is located in the point with coordinates of xi .
TELE3, a cellular communication provider planned to locate three base stations so as to provide every house in the village with cellular communication. The base station having power d located in the point t provides with communication all the houses on the segment [t−d,t+d] (including boundaries).
To simplify the integration (and simply not to mix anything up) all the three stations are planned to possess the equal power of d . Which minimal value of d is enough to provide all the houses in the village with cellular communication.
输入格式
The first line contains an integer n ( 1<=n<=2⋅105 ) which represents the number of houses in the village. The second line contains the coordinates of houses — the sequence x1,x2,...,xn of integer numbers ( 1<=xi<=109 ). It is possible that two or more houses are located on one point. The coordinates are given in a arbitrary order.
输出格式
Print the required minimal power d . In the second line print three numbers — the possible coordinates of the base stations' location. Print the coordinates with 6 digits after the decimal point. The positions of the stations can be any from 0 to 2⋅109 inclusively. It is accepted for the base stations to have matching coordinates. If there are many solutions, print any of them.
输入输出样例
输入#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