网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P3964
2024-08-13
P3964 [TJOI2013] 松鼠聚会
题意给定\(n\)个点,求出一个点使得每个点到这个点的切比雪夫距离之和最小。思路首先,我们可以把题目中的切比雪夫距离转化为曼哈顿距离,因为我们知道形如\((x,y)\)点之间的曼哈顿距离等于\((x+y,x-y)\)点之间的切比雪夫距离,\((x,y)\)点之间的切比雪夫距离等于\(\le
2024-07-28
P3964 [TJOI2013] 松鼠聚会
原题链接题解对于\((a_1,b_1),(a_2,b_2)\)的切比雪夫距离,可以看做成\((\frac{a_1+b_1}{2},\frac{a_1-b_1}{2}),(\frac{a_2+b_2}{2},\frac{a_2-b_2}{2})\)的曼哈顿距离不信你分类讨论看看某一点到其他点的曼哈顿距离,等于所有小于该点和大于该点的x,y的坐标差之和code#incl