hdu 5626 Clarke and points (曼哈顿距离变换,拆点)

http://acm.split.hdu.edu.cn/showproblem.php?pid=5626

题意:给出n(1E6)个点的二维坐标,问距离最远的两个点的距离是多少。

思路:对曼哈顿距离进行变换。

先看曼哈顿距离的定义

|x1x2|+|y1y2|

拆绝对值

x1x2+y1y2x1x2+y2y1

x2x1+y1y2x2x1+y2y1

|x1+y1(x2+y2)||x1y1(x2y2)|

x1+y1xx1y1y

|x1x2||y1y2|

所以原要求1转化为

max(|x1x2|,|y1y2|)<=c

然后分别对x,y排序即可..最大的距离一定是y[n-1]-y[0]或者x[n-1]-x[0]

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz