Minimize sum of distances.

Revision en2, by Loserinlife, 2023-06-12 14:00:54

Define the distance between two points i, j max(|xi, xj|, |yi — yj|). Given n points (xi, yi). Find a point (X, Y) so that the sum of distances from this point to n points is minimized.

N <= 1e5

xi, yi <= 1e9

Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Loserinlife 2023-06-12 14:00:54 5 Tiny change: 'nimized.\nN <= 1e5\nxi, yi <' -> 'nimized.\n\nN <= 1e5\n\nxi, yi <'
en1 English Loserinlife 2023-06-12 13:59:20 266 Initial revision (published)