HDU 5626 Clarke and points 平面两点曼哈顿最远距离

这是一道计算几何的题目，可以使用枚举或者二分答案来解决。

首先，我们可以将所有点按照横坐标从小到大排序，然后对于每个点，计算它和之前的每个点的曼哈顿距离，取最大值即可。这样的时间复杂度为 $O(n^2)$，可以通过此题。

还有一种更优秀的做法是二分答案。我们可以二分最大的曼哈顿距离 $mid$，然后判断是否存在两个点之间的曼哈顿距离大于等于 $mid$。具体做法是，我们维护当前横坐标最小的点和横坐标最大的点，然后分别向左和向右扫描，如果当前点与横坐标最小的点的横坐标之差大于等于 $mid$，那么我们就将横坐标最小的点向右移动，否则将当前点向右移动。同理，如果当前点与横坐标最大的点的横坐标之差大于等于 $mid$，那么我们就将横坐标最大的点向左移动，否则将当前点向左移动。最后如果找到了两个点之间的曼哈顿距离大于等于 $mid$，那么就说明存在一个合法解，否则不存在。这样的时间复杂度为 $O(n\log n)$。

代码实现：