Last Updated: 6 Feb, 2021

Optimum Location

Hard

Asked in company

Solve now

Problem statement

You are given a straight line on a 2D plane in the form of (ax + by + c = 0) and an array of points of the form (Xi, Yi). Your task is to find a point on the given line for which the sum of distances from this point to the given array/list of points is minimum.

For Example :

optimum_location_example

Here the equation for the given line is x - y = 0, i.e. a = 1, b = -1 and c = 0. 
There are two points, i.e. (-1, 1) and (1, -1).

So, the point on the line that has minimum distances from the points is (0, 0). The sum of distances is sqrt(1 + 1) + sqrt(1 + 1) = sqrt(2) + sqrt(2) = 2.83 (rounding to 2 decimal digits).

Input format :

The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case contains three space-separated integers denoting a, b and c, respectively, representing the equation of the given line as mentioned above.

The second line of each test case contains a single integer N, denoting the number of coordinates.

Then N lines follow. Each line contains two space-separated integers denoting the x-coordinate and the y-coordinate of the point, respectively.

Output format :

For each test case, print the minimum possible distance.
Your answer will be considered correct if its absolute or relative error doesn’t exceed 10^-6.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
1 <= N <= 3000
-100 <= a, b, c, points[i].x, points[i].y <= 100 and (a != 0, b != 0) 

Time limit: 1 second

Solve now

Approaches

01 Approach

Let’s take a point on the given line which is at an infinite distance from the origin. So, the distances of this point from the given set of points will be large and the sum will be equal to infinite. As we move along the line towards the range of points, this sum starts decreasing gradually.

Then as we move again towards infinity in the opposite direction, the distances start increasing and the sum also reaches infinity. So, this means the sum is minimum at a particular point, and it starts increasing when we move in either direction on the line. If we plot the distance curve’s sum, it looks like a U-shaped curve as stated in the below figure.

So, our idea is to select a search range and search for the optimum points in that range. However, we can’t use linear search as the distances are not necessarily integers. We can’t use binary search as well as the U-shaped curve is not monotonically increasing or decreasing. So, we have to use a ternary search to find the optimum point.

So, we take two values low and high. Initially low contains a very small value and high contains a very large value. These two values denote the range of X-coordinates of the points on the lines. Then we take mid1 and mid2, where mid1 is located at 1/3rd of the search space, and mid2 is located at 2/3rd. Find the Y-coordinate of the point on the line whose X-coordinate is mid1 and mid2 and then find the sum of the distances of the given set of points from this point. We compare both the distances and update the search space accordingly. We keep on doing the above step until the difference between low and high is negligible.

Steps:

Take two variables of double data type named as low and high and initialize them to -10^6 and 10^6 respectively.
While (high - low > (10^(-6))) do:
- Create two variables of double data type named mid1 and mid2.
- Initialize mid1 as low + (high - low) / 3 and mid2 as high - (high - low) / 3.
- We create another function to find the sum of distances of a point to all the points in the points array. Let’s name this function as findSumOfDistances(line, points, x).
- Store the sum of distances in distance1 and distance2 respectively, i.e. distance1 = findSumOfDistances(line, points, mid1) and distance2 = findSumOfDistances(line, points, mid2).
- If distance1 < distance2, then make high = mid2.
- Else, make low = mid1.
Finally, as we come out of the loop, take a variable of type double, let’s call it x, which is the X-Coordinate of the optimum point. Make x = (low + high) / 2.
Then, finally return findSumOfDistances(line, points, x).
Note that here the initial values of low and high are given just for the sake of simplicity. We can improve this search space further by drawing perpendicular lines from all the points in the points array to the given line.
Then we can initialize the values of low and high according to the X-Coordinates of the intersection points of perpendicular lines with the given line.

double findSumOfDistances(line, points, x):

Create a variable of the double data type to store the sum of distances and initialize it to 0, i.e. double sum = 0.
Find the Y-Coordinate of the point on the given line using the equation, i.e. y = -1/b(a * x + c).
Run a loop i = 0 to N and do:
- sum = sum + sqrt ((x - points[i].x)^2 + (y - points[i].y)^2).
Finally, return the sum.

Solve now