New update is available. Click here to update.

Ninja’s Service Center

Posted: 27 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
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