本文主要是介绍HDU 4312 切比雪夫转化 曼哈顿距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：从给出的点中 选出一个点作为中心 ，求别的点距这个点的最小距离的和。
思路： 根据题意 可以知道 切比雪夫 d[i]=max(|xi-x|,|y-yi|),曼哈顿距离：d[i]=|y2-y1|+|x2-x1|；然后就是从切比雪夫转化曼哈顿形式，坐标逆时针旋转 45度 ，即x1=x0-y0;y1=x0+y0; 但是 因为 得出来的新坐标 扩大√2倍，那么在这个曼哈顿里 就是2倍 ，按着曼哈顿距离算出最小答案 然后除以2 就是正确答案了
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
struct dd
{ll x,y;int w;
}dot[100000+100];
int n;ll sumx[100000+100],sumy[100000+100];
inline bool cmpx(dd a,dd b){if (a.x==b.x) {return a.y<b.y;}return a.x<b.x;
}
inline bool cmpy(dd a,dd b){if (a.y==b.y) {return a.x<b.x;}return a.y<b.y;
}
int main(int argc, const char * argv[]) {int t;cin>>t;sumx[0]=sumy[0]=0;while (t--) {scanf("%d",&n);ll x,y;for (int i=1; i<=n; ++i) {scanf("%lld%lld",&x,&y);dot[i].x=x-y;dot[i].y=x+y;}sort(dot+1,dot+n+1,cmpx);for (int i=1;i<=n ; ++i) {dot[i].w=i;sumx[i]=sumx[i-1]+dot[i].x;}sort(dot+1,dot+n+1,cmpy);for (int i=1; i<=n; ++i)sumy[i]=sumy[i-1]+dot[i].y;ll ans=1e17;for (int i=1; i<=n; ++i) {// cout<<dot[i].x<<" "<<dot[i].y<<" "<<dot[i].w<<" ";ll ty=i*dot[i].y-sumy[i]+(sumy[n]-sumy[i])-(n-i)*dot[i].y;ll tx=dot[i].w*dot[i].x-sumx[dot[i].w]+(sumx[n]-sumx[dot[i].w])-(n-dot[i].w)*dot[i].x;ans=min(ans,tx+ty);//cout<<tx+ty<<endl;}printf("%lld\n",ans/2);}return 0;
}
这篇关于HDU 4312 切比雪夫转化 曼哈顿距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
