Ninja’s Service Center

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
15 upvotes
Asked in companies
AdobeeBayUber

Problem statement

Ninja wants to start a service center in town. But people being quite lazy these days, he decided to open the service center in such a place that the sum of the euclidian distance of his service center from all his customer’s location is minimum. Ninja has positions of all its customer in a 2D map, but Ninja doesn’t know how to minimize the euclidian distance. Being his business advisor your task is to help Ninja find a suitable position for his service center.

Given a 2-D array ‘location’ where locations[ i ][ 0 ] and location[ i ][ 1 ] denotes the x and y coordinates of position of ‘i-th’ person.You need to return the minimum sum of Euclidian distance of Ninja’s service center from all customers.

The euclidian distance of a point [ x2, y2 ] from [ x1,y1 ] is given as

Note : 
You need to round up your answer to the nearest three decimal places.
For Example : 
If the position of the customers is [ [ 1,0 ], [ 4,0 ], [ 6,0 ] ], then if Ninja opens his service center at [ 4,0 ] then he will get the minimum sum of euclidian distance = 5.000  from all customers.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains ‘T’ denoting the number of test cases.

The first line of each test case contains ‘N’ denoting the number of customers.

The next ‘N’ lines contain two space-separated integers ‘ x ’ and ‘ y ’ denoting the coordinates of the position of the customers.
Output Format : 
For each test case, print a single integer denoting the minimum sum of Euclidian distance.

Print your answer up to the nearest three decimal places.

Print the output of each test case in a separated line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^3
0 <= location[ i ][ 0 ], location[ i ][ 1 ] <= 10^3

Where  location[ i ][ 0 ], location[ i ][ 1 ] denotes the ‘ x ’ and ‘ y ’ coordinates of the position of customers.

Time Limit : 1 sec
Sample Input 1 :
2
3
2 0
0 0
1 1
1
3 4
Sample Output 1 :
2.733
0.000
Explanation Of Sample Input 1 :
Test Case 1: If NInja opens his service center at [ 1,0 ] then he will get a sum of euclidian distances = 3. But if he opens his center at [ 1, 0.5773 ] then he will get a minimum sum of distances = 2.73205. Round to the nearest three decimal places = 2.733

Test Case 2: There is only one customer so the minimum distance can be ‘0’.
Sample Input 2 :
2
3
2 2
3 4
4 1
2
5 3
3 2
Sample Output 2 :
4.320
2.237
Hint

 Do you know about geometric median??

Approaches (1)
Geometric Median

We will use the concept of the geometric median to solve this problem.

If we are given ‘N’ points in the 2-D plane then a point ‘p’ whose sum of distances from all the points in the 2-D plane is minimum is known as the geometric median.

This is exactly the same that we have to do to solve the problem. The approach to find the geometric median is as - 

  • Take a pair  ‘curPoint’ that will store the coordinates of a point and a variable ‘minDis’ that will store the minimum sum of distances from a point to all other points.
  • We will first calculate the centroid of all the points and store this centroid point in ‘curPoint’ and store the sum of distances of this ‘centroid’ from all the points in ‘minDis’.
  • Assume every customer’s position to be a geometric median and calculate the sum of the euclidian distance from all points. If any points give a minimum distance, update ‘curPoint’ and ‘minDis’.
  • Now we will take a variable ‘shift’ and initialize it to some value let’s say 1000.
  • We will move our ‘curPoint’ by this ‘shift’ value in all the four directions and if the  new points obtained in any of the four directions will give less value of the sum of distances than ‘minDis’ then we will update ‘curPoint’ and ‘minDis’
  • If we do not get a point in any of the four directions that are minimizing our result, then we will divide the ‘shift’ value by 2 because we might have shifted too much and we need to look closer to the point.
  • We will continue to add this ‘shift’ value until the shift value is greater than the value of minShift (let’s say minShift = 0.01).
  • After this loop ends i.e ‘shift’ value becomes less than ‘minShift’ we will get the minimum sum of distances stored in ‘minDis’.

 

Algorithm

 

  • Take a pair  ‘curPoint’ that will store the point that we are assuming the geometric median and a variable ‘minDis’.
  • Find the coordinates of the centroid of all the points.
    • curPoint = coordinates of centroid.
    • minDis = sum of distances of centroid to all the points.
  • Run a loop i : 0 to N - 1
    • Calculate the sum of distances assuming location[ i ] be the geometric median.
    • Update ‘minDis’ and ‘curPoint’ if a distance less than ‘minDis’ is obtained.
  • Take a 2-D array ‘directions’ that will store move in all four directions.directions [ [ 0,1 ], [ 1, 0 ], [ -1, 0 ] , [ 0, -1 ] ].
  • Take a variable ‘shift’ with an initial value = 1000 and a variable ‘minShift’ with an initial value of 0.01.
  • Run a loop until shift > minShift
    • Initialize a pair  ‘newPoint’ and a variable ‘flag’ with an initial value of 0.
    • Run a loop i: 0 to 3 to check points in all four directions.
      • newPoint.first = directions[ i ][ 0 ].
      • newPoint.second = directions[ i ][ 1 ].
      • Calculate the sum of the distance of ‘newPoint’ with all points.
      • If this distance is less than ‘minDis’ then update ‘curPoint’ and ‘minDis’And make flag value 1.
    • If flag = 0, it means we have not found any point that minimizes the sum of distance so divide ‘shift’ by 2.
  • Return ‘minDis’.
Time Complexity

O( N^2 ), where ‘N’ is the number of customers.

 

We are calculating the sum of the euclidian distance from all customer’s locations. Therefore time complexity is O( N^2).

Space Complexity

O(1)

 

We have not used any extra space. Therefore space complexity is O(1).

Code Solution
(100% EXP penalty)
Ninja’s Service Center
Full screen
Console