两点(x1,y2)与(x2,y2)之间的曼哈顿距离为|x1-x2|+|y1-y2|在仩图中,红蓝黄三色线都表示两黑点间的曼哈顿距离
现在Uncle Bird有n个点(xi,yi),显然你可以算出任意两个点之间的曼哈顿距离。
那么问题来了:请你幫Uncle Bird算出任意两点之间曼哈顿距离的最大值
小提示:因为点的数量很多(10^5),不能直接枚举两点计算距离需要一个小小的trick。
每组测试数据的第一行输入一个正整数n(2<=n<=100000)表示点的个数。
distance的一个性质考虑取一个在所有点左下角的点为基准A(x0,y0),那么对于满足x1<=x2和y1<=y2的点对B(x1,y1)和C(x2,y2)BC(曼哈顿距离,下同)=AC-AB。同理取右下角基准点可以处理x1<=x2和y1>=y2的的点对的距离。这样将两两点之间曼哈顿距离转换為到基准点的距离之差。那我们只需要用到基准点距离最大值减去最小值就得到了两点之间距离最大值。对两个基准分别做这个操作然後取较大的就可以了复杂度o(n)。