You are given an array \(A\) of \(N\) points in a \(2-D\) plane, which denotes the location of houses of students. The students decided to meet at one of the houses to study together.
For travelling from a point in the plane \([ X_1, Y_1 ]\) to the point \([ X_2, Y_2]\), a student needs to travel a total distance of \(abs|X_1 - X_2| + abs|Y_1- Y_2|\) i.e. the sum of the absolute difference between the differences in both the \(X\) and the \(Y\) coordinates.
Initially all the students are at their own house and they decide to meet in the house whose location is present in the array \(A\) such that the sum of total distances covered by other students to reach this house is minimum.
Input Format:
- The first line contains an integer \(T\), which denotes the number of test cases.
- The first line of each test case contains an integer \(N\), denoting the number of points in the plane.
- The next \(N\) lines of each test case contains \(2\) space-separated integers, \(X\) and \(Y\), the coordinates of the houses on the plane.
Output Format:
For each test case, print the minimum distance travelled by all the students provided they choose the most optimal house.
Constraints:
\(1 <= T <= 10\)
\(1 <= N <= 10^5\)
\(1 <= X, Y <= 10^3\)
For first test case:
If the students meet at the house index \(3\) i.e. \(A[3] = [5,5]\), then the total distance covered will be,
For student indexed 1, abs(4-5) + abs(5-5) = 1.
For student indexed 2, abs(5-5) + abs(4-5) = 1.
For student indexed 3, abs(5-5) + abs(5-5) = 0.
Hence, the answer is \(2\).
For second test case:
If the students meet at the house index \(2\) i.e. \(A[2] = [7,8]\), then the total distance covered will be,
For student indexed 1, abs(9-7) + abs(9-8) = 3.
For student indexed 2, abs(7-7) + abs(8-8) = 0.
Hence, the answer is \(3\).
Another possible house is \(A[1]= [9,9]\), then the total distance covered will be,
For student indexed 1, abs(9-9) + abs(9-9) = 0.
For student indexed 2, abs(7-9) + abs(8-9) = 3.
Hence, the answer is \(3\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor