51nod3143 整装待发！

51nod3143 整装待发！

3143 整装待发！

n位战士即将奔赴战场，他们每个人都有一个攻击值和一个防御值，现在你想设计一种装备给这n位战士，如果这件装备的攻击值为A，防御值为B，那么对于第ii位战士这件装备的不匹配度为 ，总的不匹配度之和为

输入

第一行一个整数n表示战士的数量
接下来n行，每行两个整数x[i],y[i]表示这个战士的攻击值和防御力

输出

一个整数表示最小的不匹配度之和

数据范围

20% 2 <= n <= 5
50% 2 <= n <= 1000
100% 2 <= n <= 100000

输入样例

输入样例1：
3
1 2
2 1
3 3
输入样例2：
4
0 0
0 2
2 0
2 2
输入样例3：
4
0 0
1 0
0 1
1 1

输出样例

输出样例1：
3
输出样例2：
4
输出样例3：
3

解析：

就是二维平面上一堆点 ， 一个点使得所有点到这个点的切比雪夫距离最小。
转化一下转成曼哈顿坐标就直接去中位数就行 ， 注意坐标要是整点 ， 要是不是整点的话想四个方向移动一下看哪个最小。

放代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int N=1e5+10;
double a[N],b[N],c[N],d[N];
int k[N],q[N];
int main()
{int n;cin>>n;for(int i=0; i<n; i++){double x,y;scanf("%lf%lf",&x,&y);k[i]=x;q[i]=y;a[i]=(x+y)/2;//排序求中位数的曼哈顿距离c[i]=(x+y)/2;b[i]=(x-y)/2;//排序求中位数的曼哈顿距离d[i]=(x-y)/2;}sort(a,a+n);sort(b,b+n);double  x,y;ll sum=0;if(n%2==1)//求中位数{x=a[n/2];y=b[n/2];}else{x=(a[n/2]+a[n/2-1])/2;y=(b[n/2]+b[n/2-1])/2;}if((x+y)==(int)(x+y)&&(x-y)==(int)(x-y))//恰好中位数是整数{for(int i=0; i<n; i++){sum+=abs(c[i]-(int)x)+abs(d[i]-(int)y);}cout<<sum<<endl;}else{int A=(x+y);int B=(x-y);ll ans1=0,ans2=0,ans3=0,ans4=0;//不是整数的四种情况for(int i=0; i<n; i++){ans1+=max(abs(k[i]-(int)A),abs(q[i]-(int)B));}for(int i=0; i<n; i++){ans2+=max(abs(k[i]-(int)A-1),abs(q[i]-(int)B));}for(int i=0; i<n; i++){ans3+=max(abs(k[i]-(int)A-1),abs(q[i]-(int)B-1));}for(int i=0; i<n; i++){ans4+=max(abs(k[i]-(int)A),abs(q[i]-(int)B-1));}sum=min(min(min(ans1,ans2),ans3),ans4);cout<<sum<<endl;}return 0;
}