Place New Stations to Minimize the Widest Gap

### Problem stations contains strictly increasing positions on the x-axis. Add exactly k stations at arbitrary real positions, including noninteger positions. Minimize the largest distance between adjacent stations and return that minimum. An answer within 0.000001 of the exact optimum is accepted. ```cpp class Solution { public: double minmaxGasDist(vector<int>& stations, int k); }; ``` ### Examples **Example 1:** ```text stations = [0,2,4,6,8,10,12,14,16,18], k = 9 Output: 1.0 Explanation: Split each of the nine gaps in half; total length 18 over18 final gaps also proves the lower bound. ``` **Example 2:** ```text stations = [0,1,2,3,4,5,6,7,8,12], k = 1 Output: 2.0 Explanation: Split the final gap of length4 into two gaps of length2; one new station cannot reduce that gap below2. ``` ### Constraints - There are 10 through 2000 original stations, strictly ordered by position. - Positions lie in [0,100000000]. - Add between 1 and 1000000 stations. - The accepted absolute answer error is at most 0.000001. ### Contract considerations Retain the double return type, real-valued placement and absolute tolerance. ```hint Read the boundary condition How many subdivisions of one gap are needed for a proposed maximum length? ``` ### Boundary reminders Retain the double return type, real-valued placement and absolute tolerance.