首页 > 代码库 > BZOJ 3210 花神的浇花集会 计算几何- -?
BZOJ 3210 花神的浇花集会 计算几何- -?
题目大意:给定平面上的n个点,求一个点到这n个点的切比雪夫距离之和最小
与3170不同的是这次选择的点无需是n个点中的一个
首先将每一个点(x,y)变为(x+y,x-y) 这样新点之间的曼哈顿距离的一半就是原点之间的切比雪夫距离
因为曼哈顿距离中横纵坐标不互相干扰,因此我们能够将横纵坐标分开处理
每一维要选一个坐标 到其它全部坐标的绝对值之和相等 非常easy想到中位数
可是直接选择中位数得到的点可能横纵坐标奇偶性不同 这样代回原点中发现不是整点
因此假设得到的点横纵坐标奇偶性同样直接输出距离 不同的话选择周围的四个点进行判定 选择最小的距离输出就可以
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 using namespace std; int n,X[M],Y[M]; long long Check(int x,int y) { int i; long long re=0; for(i=1;i<=n;i++) re+=abs(x-X[i])+abs(y-Y[i]); return re; } int main() { int i,x,y; cin>>n; for(i=1;i<=n;i++) { scanf("%d%d",&x,&y); X[i]=x+y;Y[i]=x-y; } sort(X+1,X+n+1); sort(Y+1,Y+n+1); x=X[n+1>>1]; y=Y[n+1>>1]; if( ~(x^y)&1 ) cout<<Check(x,y)/2<<endl; else cout<<min(min(Check(x+1,y),Check(x-1,y)),min(Check(x,y+1),Check(x,y-1)))/2<<endl; return 0; }
BZOJ 3210 花神的浇花集会 计算几何- -?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。