BZOJ3170:[Tjoi 2013]松鼠聚会&&BZOJ3210:花神的浇花集会 坐标重构

题目大意:

平面上有\(n\)个点,第\(i\)个点的坐标为\((x_i,y_i)\),两个点\(i,j\)之间的距离为\(max(|x_i-x_j|,|y_i-y_j|)\),求哪个点到其他所有点的距离之和最小.

思路:

首先我们有一个结论:

\[max(|a+b|,|a-b|)=|a|+|b|\]

只需分类讨论便可以证明这个结论.

我们考虑对坐标进行重构,对于点\(i\),令\(x_i'=x_i+y_i,y_i'=x_i-y_i\).

则现在两个点\(i,j\)之间的距离为:

\[max(|x_i-x_j|,|y_i-y_j|)=max(|\frac{x_i'+y_i'}{2}-\frac{x_j'+y_j'}{2}|,|\frac{x_i'-y_i'}{2}-\frac{x_j'-y_j'}{2}|)=|\frac{x_i'-x_j'}{2}|+|\frac{y_i'-y_j'}{2}|\]

于是我们只需要重构坐标,分别算出两个维上每个点的代价,最终合起来取最小值即可.

BZOJ3210同理,只不过这个中心点需要自己去确定.我们找到重构点两个维度的中位数作为基准坐标,不过不一定就能拿这个作为答案.只有两个数奇偶相同才能作为答案,否则不能被表示成原平面上的整点.在基准坐标附近枚举便可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
typedef long long LL;
  
#define N 100010
int x[N],y[N];
  
struct Case{
    int Comp,lab;
    Case(){}
    Case(int _Comp,int _lab):Comp(_Comp),lab(_lab){}
    bool operator<(const Case&B)const{return Comp<B.Comp;}
}S[N];
  
typedef long long LL;
LL res[N];
  
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
  
    int n,t;scanf("%d",&n);
    register int i,j;for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]),t=x[i],y[i]-=t,x[i]+=y[i]+t,y[i]=-y[i];
    //for(i=1;i<=n;++i)printf("%d %d\n",x[i],y[i]);
    LL add;
    for(i=1;i<=n;++i)S[i]=Case(x[i],i);
    sort(S+1,S+n+1);
    for(add=0,i=1;i<=n;++i)res[S[i].lab]+=(LL)(i-1)*S[i].Comp-add,add+=S[i].Comp;
    for(add=0,i=n;i>=1;--i)res[S[i].lab]+=add-(LL)(n-i)*S[i].Comp,add+=S[i].Comp;
    for(i=1;i<=n;++i)S[i]=Case(y[i],i);
    sort(S+1,S+n+1);
    for(add=0,i=1;i<=n;++i)res[S[i].lab]+=(LL)(i-1)*S[i].Comp-add,add+=S[i].Comp;
    for(add=0,i=n;i>=1;--i)res[S[i].lab]+=add-(LL)(n-i)*S[i].Comp,add+=S[i].Comp;
  
    LL ret=1LL<<60;
    for(i=1;i<=n;++i)ret=min(ret,res[i]);
  
    cout<<ret/2;
  
    return 0;
}