Proof wanted for task
source link: https://codeforces.com/blog/entry/116363
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Proof wanted for task
The task in question is as follows: given N points on a coordinate plane, for some point A find the furthest point (manhattan disrtance) from A in the given set of N points. I know that one of the solutions to this problem is to consider only 4 points, the one with maximal (x + y) value, maximal (x — y) value, maximal (-x — y) value, maximal (y — x) value. It is guaranteed that one of these 4 points will be the furthest point from A. I can see that by doing this we maximize all of the 4 cases of the manhattan distance formula, but when we insert these 4 points into the formula it is not guaranteed that the corresponding cases we want to maximize will hold. Can anyone help me understand why this solution works?
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK