CodeForces 51C 二分搜索

校队选拔神马的事情就不说了，哥们反正是要崛起的人了！

感谢何骐的提醒。

校队选拔的时候又被二分给坑了，所以还想做几道二分搜索的题目来练练手。

C - Three Base Stations

Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Description

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 x_i coordinate. The village consists of n houses, the i-th house is located in the point with coordinates of x_i.

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.

Input

The first line contains an integer n (1 ≤ n ≤ 2· 10⁵) which represents the number of houses in the village. The second line contains the coordinates of houses — the sequence x₁, x₂, ..., x_n of integer numbers (1 ≤ x_i ≤ 10⁹). It is possible that two or more houses are located on one point. The coordinates are given in a arbitrary order.

Output

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· 10⁹ inclusively. It is accepted for the base stations to have matching coordinates. If there are many solutions, print any of them.

Sample Input

Input

4
1 2 3 4

Output

0.500000
1.500000 2.500000 3.500000

Input

3
10 20 30

Output

0
10.000000 20.000000 30.000000

Input

5
10003 10004 10001 10002 1

Output

0.500000
1.000000 10001.500000 10003.500000

初看这个题目的时候，我以为又是切蛋糕那种题目，二分一个浮点数，（事实上根据网上博客贴的代码，有人这样做也可以过）。但是后来接触到一种思路，事实上点坐标都是整数，所以站点的覆盖范围，即覆盖圆的直径，必定是一个整数，故，只要二分覆盖圆的直径，即可。

关于最后还要输出每个站点的具体坐标，一个好的方法是在二分时用个数组记录每建立一个覆盖点后，覆盖到的点的下一点。这样，求坐标的时候，还是在代码里面说吧

比较坑的是第一组数据，我为这个纠结了好久，明显的在第一组数据中，两个站点就可以覆盖4个点，第三个站点随便怎么放，但我以为一定要按样例，改来改去，都没法统一

结果发现根本就不用管这个破第一组样例，也过了。可能像这种数据，随便站点怎么放，只要能覆盖就过了吧。

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 200000
#include <algorithm>
using namespace std;
int loc[maxn+10];
int n;
int ans[4];
int fnext(int y) //用来找到当前覆盖圆覆盖后的最近一个覆盖点。
{
    int l=1,r=n+1,mid=(l+r)/2;
    while (l<r)
    {

        if (loc[mid]<=y)
            l=mid+1;
        else
            r=mid;
        mid=(l+r)/2;
    }
    return mid;
}
int ok(int x)
{
    int i,j;
    int z=1;
    for (i=1; i<=3; i++)
    {

        z=fnext(loc[z]+x);
        ans[i]=z; //用这个数组来记录覆盖圆的下一个点。
        //cout<<x<<" "<<z<<endl;
        if (z>=n+1) return 1;
    }

    return 0;
}
int main()
{

    while (scanf("%d",&n)!=EOF)
    {
        int i,j,k;
        for (i=1; i<=n; i++)
        {
            scanf("%d",&loc[i]);
            //cout<<loc[i]<<endl;
        }
        sort(loc+1,loc+n+1);
        //loc[n+1]=loc[n];
        int r=(loc[n]-loc[1]);
        int l=0,mid;
        while (l<r) //二分覆盖圆的直径
        {
            mid=(r+l)/2;
            if (ok(mid)) r=mid;
            else l=mid+1;
        }
        ok(l);
        //cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<endl;
        double radius=l*1.0/2.0;
        double radar1=(loc[ans[1]-1]+loc[1])*1.0/2.0;
        double radar2=(loc[ans[2]-1]+loc[ans[1]])/2.0;//前点加后点再除以2的方式得到圆心坐标
        double radar3=(loc[ans[3]-1]+loc[ans[2]])/2.0;
        printf("%.6f
",radius);
        printf("%.6f ",radar1);
        printf("%.6f ",radar2);
        printf("%.6f
",radar3);
    }
    return 0;
}