4312专题

HDU 4312 切比雪夫转化 曼哈顿距离

题目大意:从给出的点中 选出一个点作为中心 ,求别的点距这个点的最小距离的和。 思路:       根据题意 可以知道 切比雪夫 d[i]=max(|xi-x|,|y-yi|),曼哈顿距离:d[i]=|y2-y1|+|x2-x1|;然后就是从切比雪夫转化曼哈顿形式,坐标逆时针旋转 45度 ,即x1=x0-y0;y1=x0+y0; 但是 因为 得出来的新坐标 扩大√2倍,那么在这个曼哈顿里 就是2