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}$

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.