Optimum location of point to minimize total distance | A JavaScript program to find optimum location and total cost ; structure defining a point ; structure defining a line of ax + by + c = 0 form ; method to get distance of point ( x , y ) from point p ; Utility method to compute total distance all points when choose point on given line has x - coordinate value as X ; calculating Y of chosen point by line equation ; Utility method to find minimum total distance ; loop until difference between low and high become less than EPS ; mid1 and mid2 are representative x co - ordiantes of search space ; if mid2 point gives more total distance , skip third part ; if mid1 point gives more total distance , skip first part ; compute optimum distance cost by sending average of low and high as X ; method to find optimum cost ; converting 2D array input to point array ; Driver Code
function sq ( x ) { return x * x ; } let EPS = ( 1e-6 ) + 1 ; let N = 5 ; class point { constructor ( x , y ) { this . x = x ; this . y = y ; } } class line { constructor ( a , b , c ) { this . a = a ; this . b = b ; this . c = c ; } } function dist ( x , y , p ) { return Math . sqrt ( sq ( x - p . x ) + sq ( y - p . y ) ) ; } function compute ( p , n , l , X ) { let res = 0 ; let Y = - 1 * ( l . c + l . a * X ) / l . b ; for ( let i = 0 ; i < n ; i ++ ) res += dist ( X , Y , p [ i ] ) ; return res ; } function findOptimumCostUtil ( p , n , l ) { let low = - 1e6 ; let high = 1e6 ; while ( ( high - low ) > EPS ) { let mid1 = low + ( high - low ) / 3 ; let mid2 = high - ( high - low ) / 3 ; let dist1 = compute ( p , n , l , mid1 ) ; let dist2 = compute ( p , n , l , mid2 ) ; if ( dist1 < dist2 ) high = mid2 ; else low = mid1 ; } return compute ( p , n , l , ( low + high ) / 2 ) ; } function findOptimumCost ( points , l ) { let p = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) p [ i ] = new point ( points [ i ] [ 0 ] , points [ i ] [ 1 ] ) ; return findOptimumCostUtil ( p , N , l ) ; } let l = new line ( 1 , - 1 , - 3 ) ; let points = [ [ - 3 , - 2 ] , [ - 1 , 0 ] , [ - 1 , 2 ] , [ 1 , 2 ] , [ 3 , 4 ] ] ; document . write ( findOptimumCost ( points , l ) ) ;