Okay, so in this question my first instinct was that it's a 2D problem. I have been given multiple points on a 2D plane and I have to find the points whose summation distance is minimum from all the given points. My initial guess was to check all the points enclosed in the polygon formed by the given points and find out which points have the min summation distance from all given points but it obviously gave TLE. Eventually, I looked at the solution.
From the solution, I realized that I had to make two observations: 1. The way of measuring distance is "summation distance" It is just |x2-x1| +|y2-y1| and not sqrt((x2-x1)^2+(y2-y1)^2). What this allows us to see is that if I have a point p1, then it's summation distance from all given points(q1,q2,q3...qn) is
|qx1-px1| + |qy1-py1| + |qx2-px1| + |qy2-py1| + |qx3-px1| + |qy3-py1| + ... + |qxn-px1|+ |qyn-py1|
=>
(|qx1-px1| + |qx2-px1| + |qx3-px1| + ... + |qxn-px1|) + (|qy1-py1| + |qy2-py1| + |qy3-py1| + ... + |qyn-py1|)
=>
Summation_distance_on_the_x_axis + Summation_distance_on_the_y_axis
Thus, this becomes similar to solving two one dimensional problems, rather than one two-dimensional problem.
- The second observation is knowing how to solve the problem for one dimension. Now this turns out, it's a well known problem and the answer is that all the points between the left and right median have the same summation distance from all points. I dont know how to prove this yet. But emperically this seems true.
Hence, after we get all the points on the x and y axis(Lets put them in an x-list and y-list) that satisfy this condition in their individual axes, we multiply the number of points, because every combination of two points from the x-list and y-list will give a 2D point that have minimum summation distance from all points.
