Given a set of coordinates points of the form [p, q] and a line L of the form ax + by + c = 0. The task is to find a point on a given line for which the sum of distances from a given set of coordinates is minimum. 
 
Example 1:
Input:
L = {1, -1, -3}
points[] = {{-3, 2}, {-1, 0}, 
            {-1, 2}, {1, 2}, {3, 4}}
Output: 20.77
Explanation: In above figure optimum location of 
point of x - y - 3 = 0 line is (2, -1), whose 
total distance with other points is 20.77, 
which is minimum obtainable total distance.
Example 2:
Input:
L = {2, 1, 4}
points[] = {{-1, 2}, {1, 3},{2, 4}}
Output: 11.20
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findOptimumCost() which takes a line L and coordinates and returns an double up to 2 decimal places as output.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}
-10^{3 }<= point[i] <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: from typing import List





from typing import List





class Solution:

    def findOptimumCost(self, line : List[int], n : int, points : List[List[int]]) -> float:

        # code here

        



Solutions:
from typing import List
from math import sqrt

class Solution:

	def distance(self, x1, x2, y1, y2):
		x_diff = (x1 - x2) * (x1 - x2)
		y_diff = (y1 - y2) * (y1 - y2)
		return sqrt(x_diff + y_diff)

	def compute(self, x, line, n, points):
		(a, b, c) = line
		y = -(a * x + c) / b
		res = 0.0
		for (x1, y1) in points:
			res += self.distance(x, x1, y, y1)
		return res

	def findOptimumCost(self, line: List[int], n: int, points: List[List[int]]) -> float:
		low = -1000
		high = 1000
		eps = 0.001
		if line[1] == 0:
			return float('inf')
		while high - low > eps:
			mid1 = low + (high - low) / 3
			mid2 = high - (high - low) / 3
			dist1 = self.compute(mid1, line, n, points)
			dist2 = self.compute(mid2, line, n, points)
			if dist1 < dist2:
				high = mid2
			else:
				low = mid1
		avg = (low + high) / 2
		return self.compute(avg, line, n, points)


from typing import List
from typing import List
import math as m

class Solution:

	def findOptimumCost(self, line: List[int], n: int, points: List[List[int]]) -> float:
		if line[1] == 0:
			return m.inf
		low = -1000000.0
		high = 1000000.0

		def distance(x, y, x_, y_):
			diff1 = (x - x_) * (x - x_)
			diff2 = (y - y_) * (y - y_)
			return m.sqrt(diff1 + diff2)

		def compute(x):
			(a, b, c) = (line[0], line[1], line[2])
			y = -(a * x + c) / b
			res = 0.0
			for point in points:
				res += distance(point[0], point[1], x, y)
			return res
		for i in range(81):
			mid = low + (high - low) / 2
			val1 = compute(mid)
			val2 = compute(mid + 0.001)
			if val1 < val2:
				high = mid
			else:
				low = mid
		return compute(low)


from typing import List
import math

class Solution:

	def calculate_distance(self, line, n, points, x):
		if line[1] == 0:
			y = float('inf')
		else:
			y = -1 * (line[2] + line[0] * x) / line[1]
		dis = 0
		for point in points:
			dis += math.sqrt((point[0] - x) ** 2 + (point[1] - y) ** 2)
		return dis

	def findOptimumCost(self, line: List[int], n: int, points: List[List[int]]) -> float:
		l = -1000
		r = 1000
		mid1 = 0
		mid2 = 0
		ap = 0.001
		while abs(r - l) >= ap:
			mid1 = l + (r - l) / 3
			mid2 = r - (r - l) / 3
			fmid1 = self.calculate_distance(line, n, points, mid1)
			fmid2 = self.calculate_distance(line, n, points, mid2)
			if fmid1 > fmid2:
				l = mid1
			elif fmid1 < fmid2:
				r = mid2
			else:
				l = mid1
				r = mid2
		return self.calculate_distance(line, n, points, r)


from typing import List
from typing import List
import math

class Solution:

	def findOptimumCost(self, line: List[int], n: int, points: List[List[int]]) -> float:
		if line[1] == 0:
			return float('inf')

		def dist(x):
			res = 0
			y = (line[0] * x + line[2]) / -line[1]
			for (i, j) in points:
				res += math.sqrt((x - i) ** 2 + (y - j) ** 2)
			return res

		def soln():
			l = -1000
			h = 1000
			while h - l >= 0.001:
				mid1 = l + (h - l) / 3
				mid2 = h - (h - l) / 3
				dist1 = dist(mid1)
				dist2 = dist(mid2)
				if dist1 < dist2:
					h = mid2
				else:
					l = mid1
				diff = h - l
			return dist(l)
		return soln()


from typing import List
import math

class Solution:

	def distance(self, x1, y1, x2, y2):
		dist = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
		return dist

	def allDistances(self, line, points, x):
		ans = 0
		y = (line[2] + line[0] * x) / (-1 * line[1])
		for i in points:
			ans += self.distance(x, y, i[0], i[1])
		return ans

	def findOptimumCost(self, line: List[int], n: int, points: List[List[int]]) -> float:
		(l, r) = (-10 ** 6, 10 ** 6)
		thrs = 1e-06
		if line[1] == 0:
			return float('inf')
		while r - l > thrs:
			cut1 = l + (r - l) / 3
			cut2 = r - (r - l) / 3
			dist1 = self.allDistances(line, points, cut1)
			dist2 = self.allDistances(line, points, cut2)
			if dist1 < dist2:
				r = cut2
			else:
				l = cut1
		return self.allDistances(line, points, (l + r) / 2)


from typing import List
import math
from typing import List

class Solution:

	def fun1(self, x, y, a, b):
		return math.sqrt((x - a) * (x - a) + (y - b) * (y - b))

	def fun(self, line: List[int], pts: List[List[int]], n: int, x):
		y = (-(line[0] * x) - line[2]) / line[1]
		sum = 0
		for i in range(n):
			sum += self.fun1(x, y, pts[i][0], pts[i][1])
		return sum

	def findOptimumCost(self, line: List[int], n: int, points: List[List[int]]) -> float:
		eps = 1e-06
		l = -1000000.0
		r = 1000000.0
		if line[1] == 0:
			return float('inf')
		while r - l > eps:
			mid1 = l + (r - l) / 3
			mid2 = r - (r - l) / 3
			dis1 = self.fun(line, points, n, mid1)
			dis2 = self.fun(line, points, n, mid2)
			if dis1 < dis2:
				r = mid2
			else:
				l = mid1
		return self.fun(line, points, n, (l + r) / 2)


from typing import List
from typing import List
import math

class Solution:

	def dist(self, x, y, p):
		distance = math.sqrt((x - p[0]) ** 2 + (y - p[1]) ** 2)
		return distance

	def sumOfDis(self, xOnL, l, points):
		sum = 0
		yOnL = -1 * ((l[0] * xOnL + l[2]) / l[1])
		for point in points:
			sum += self.dist(xOnL, yOnL, point)
		return sum

	def findOptimumCost(self, line: List[int], n: int, points: List[List[int]]) -> float:
		if line[1] == 0:
			return float('inf')
		leftX = -100000.0
		rightX = 100000.0
		veryLow = 0.0001
		while rightX - leftX > veryLow:
			mid1 = leftX + (rightX - leftX) / 3
			mid2 = rightX - (rightX - leftX) / 3
			sum1 = self.sumOfDis(mid1, line, points)
			sum2 = self.sumOfDis(mid2, line, points)
			if sum1 < sum2:
				rightX = mid2
			else:
				leftX = mid1
		optPoint = (leftX + rightX) / 2
		optDis = self.sumOfDis(optPoint, line, points)
		return optDis