On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = stations.length.

Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of D.

Example:

Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
Output: 0.500000
Note:

stations.length will be an integer in range [10, 2000].
stations[i] will be an integer in range [0, 10^8].
K will be an integer in range [1, 10^6].
Answers within 10^-6 of the true value will be accepted as correct.









class Solution {
public:
    double minmaxGasDist(vector<int>& A, int K) {
        double res=0.0;
        for(int i=1;i<A.size();i++){
            res=max(res,(A[i]+0.0)-A[i-1]);
        }
        
        double l=0,r=A[A.size()-1]-A[0];
        double STEP=0.0000001;
        while(r-l>=STEP){
            double mid=l+(r-l)/2;
            int cnt=0;
            for(int i=1;i<A.size();i++){
                double dif=A[i]-A[i-1];
                cnt+=(int)(dif/mid);
            }
            
            if(cnt<=K){
                res=mid;
                r=mid-STEP;
            }
            else{
                l=mid+STEP;
            }
        }
        return res;
    }
};