You are given an integer array, stations, representing the positions of existing gas stations along the x-axis. You are also given an integer k, indicating the number of additional gas stations you must add. These new gas stations can be placed at any position along the x-axis, including non-integer locations.

A penalty is the maximum distance between two adjacent gas stations after placing the k new stations. Your task is to return the smallest possible value of this penalty. An answer is correct if it is within $10^{-6}$ of the actual answer.

Constraints:

• $10 \leq$ stations.length $\leq 2000$

• $0 \leq$ stations[i] $\leq 10^8$

• The stations array is sorted in a strictly increasing order.

• $1 \leq$ k $\leq 10^{6}$

To solve this problem, we aim to make the largest gap between any two adjacent stations as small as possible by placing the given k new stations. The first idea that might come to mind is: split the current largest gap evenly. For example, if stations = [0, 1, 2, 4] and k = 1, the gaps between the adjacent stations are [1, 1, 2]. One way to reduce the current maximum gap, 2, is to place the new station at position 3, making the new stations list [0, 1, 2, 3, 4]. Now, the gaps become [1, 1, 1, 1], and the maximum gap is reduced to 1, which is the correct answer. But for larger inputs with many unequal gaps and multiple new stations, it’s not obvious which gaps to break or how to distribute the new stations.

As we don’t know where exactly to place the k new stations, we flip the problem: instead of trying to find the positions, we'll try to find the smallest possible maximum gap (let’s call it $D$) that we can achieve by placing k stations. If we haven't added any new stations yet, the current maximum gap (let's call it $M$) gives us an upper bound, i.e., $$ ...