Minimize the maximum distance between adjacent points after adding K points anywhere in between | C ++ program for the above approach ; Function to check if it is possible to add K points such that the maximum distance between adjacent points is D ; Stores the count of point used ; Iterate over all given points ; Add number of points required to be placed between ith and ( i + 1 ) th point ; Return answer ; Function to find the minimum value of maximum distance between adjacent points after adding K points any where between ; Stores the lower bound and upper bound of the given range ; Perform binary search ; Find the middle value ; Update the current range to lower half ; Update the current range to upper half ; Driver Code
#include <iostream> NEW_LINE using namespace std ; bool isPossible ( double D , int arr [ ] , int N , int K ) { int used = 0 ; for ( int i = 0 ; i < N - 1 ; ++ i ) { used += ( int ) ( ( arr [ i + 1 ] - arr [ i ] ) / D ) ; } return used <= K ; } double minMaxDist ( int stations [ ] , int N , int K ) { double low = 0 , high = 1e8 ; while ( high - low > 1e-6 ) { double mid = ( low + high ) / 2.0 ; if ( isPossible ( mid , stations , N , K ) ) { high = mid ; } else { low = mid ; } } return low ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } ; int K = 9 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << minMaxDist ( arr , N , K ) ; return 0 ; }