Minimize Max Distance to Gas Station

Statement

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

Examples