题目大意
给定n个点,找到一个点使这个点到其他所有点的切比雪夫距离之和最小。
题解
我们知道切比雪夫距离和曼哈顿距离的转化公式
(1)表示切比雪夫距离,(2)表示曼哈顿距离
我们有:
(x_1 = x_2 - y_2,y_1 = x_2 + y_2)
(x_2 = frac{x_1 + y_1}{2},y_2 = frac{x_1 - y_1}{2})
所以现在转化成曼哈顿距离了
所以我们直接枚举点即可
什么?你问我怎么计算距离和?
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 100010;
struct Node{
ll x,y;
int id;
}G[maxn];
inline bool cmp1(const Node &a,const Node &b){return a.x < b.x;}
inline bool cmp2(const Node &a,const Node &b){return a.y < b.y;}
ll a[maxn],b[maxn];
int main(){
int n;read(n);
for(int i=1,x,y;i<=n;++i){
read(x);read(y);
G[i].x = (1LL*x+y);
G[i].y = (1LL*x-y);
}sort(G+1,G+n+1,cmp1);
for(int i=1;i<=n;++i){
a[i] = a[i-1] + G[i].x;
G[i].id = i;
}sort(G+1,G+n+1,cmp2);
for(int i=1;i<=n;++i)
b[i] = b[i-1] + G[i].y;
ll ans = 1LL<<60;
for(int i=1;i<=n;++i){
ll x = (a[n] - a[G[i].id]) - (a[G[i].id] - a[G[i].id-1])*(n - G[i].id);
x += (a[G[i].id] - a[G[i].id - 1])*(G[i].id - 1) - (a[G[i].id-1]);
ll y = (b[n] - b[i]) - G[i].y*(n - i);
y += G[i].y*(i-1) - b[i-1];
if(ans > x+y) ans = x+y;
}printf("%lld
",ans>>1);
getchar();getchar();
return 0;
}