【Codeforces 685C】Optimal Point

mrsrz 12月 06, 2019

二分答案

题目大意：

给定 $n$ 个三维平面的整点，要求找到一个整点，使得给定的 $n$ 个点中，离它曼哈顿距离最远的那个点离它的曼哈顿距离最近。

题解：

显然可以二分答案。

我们可以确定出以下式子：

$\cdots \leq x+y+z\leq \cdots\\ \cdots \leq x+y-z\leq \cdots\\ \cdots \leq x-y+z\leq \cdots\\ \cdots \leq -x+y+z\leq \cdots\\$

令 $a=-x+y+z,b=x-y+z,c=x+y-z$，那么有

$a+b+c=x+y+z\\ x=\frac{b+c}2\\ y=\frac{a+c}2\\ z=\frac{a+b}2$

由于 $x,y,z$ 均为整数，所以 $a,b,c$ 奇偶性要相同。分别对奇数和偶数判断即可。

判断的时候，先令 $a,b,c$ 最小，这时 $x+y+z$ 最小。然后分别把 $a,b,c$ 改到最大或尽可能大，满足 $x+y+z$ 恰好为上限。这时的答案显然合法。

一开始时先把不等式冲突的情况判掉即可。

不等式相关信息可以在二分外面求出来。

时间复杂度 $O(n+\log w)$。

Code：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define rep(i,x,y)for(int i=(x);i<=(y);++i)
typedef long long LL;
const int N=1e5+5;
int n,T;
LL X[N],Y[N],Z[N];
LL w[8],sx,sy,sz;
inline bool check(LL k){
    rep(_,0,1){
        LL aL=-w[4]-k,bL=-w[2]-k,cL=-w[1]-k,aR=w[3]+k,bR=w[5]+k,cR=w[6]+k;
        LL sL=-w[0]-k,sR=w[7]+k;
        if((aL&1)!=_)++aL;
        if((bL&1)!=_)++bL;
        if((cL&1)!=_)++cL;
        if((sL&1)!=_)++sL;
        if((aR&1)!=_)--aR;
        if((bR&1)!=_)--bR;
        if((cR&1)!=_)--cR;
        if((sR&1)!=_)--sR;
        if(aL>aR||bL>bR||cL>cR||sL>sR||aL+bL+cL>sR||aR+bR+cR<sL)continue;
        LL a=aL,b=bL,c=cL;
        if(aR+b+c<=sR)a=aR;else a=a+(sR-a-b-c);
        if(a+bR+c<=sR)b=bR;else b=b+(sR-a-b-c);
        if(a+b+cR<=sR)c=cR;else c=c+(sR-a-b-c);
        sx=b+c>>1,sy=a+c>>1,sz=a+b>>1;
        return 1;
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(cin>>T;T--;){
        cin>>n;
        rep(i,1,n)cin>>X[i]>>Y[i]>>Z[i];
        memset(w,0x3f,sizeof w);
        rep(_1,0,1)rep(_2,0,1)rep(_3,0,1){
            LL&s=w[(_1<<2)|(_2<<1)|_3];
            rep(i,1,n){
                LL k=(X[i]*(_1?1:-1))+(Y[i]*(_2?1:-1))+(Z[i]*(_3?1:-1));
                s=min(s,k);
            }
        }
        LL l=0,r=3e18,ans=3e18;
        while(l<=r){
            const LL mid=l+r>>1;
            if(check(mid))r=(ans=mid)-1;else l=mid+1;
        }
        check(ans);
        cout<<sx<<' '<<sy<<' '<<sz<<'\n';
    }
    return 0;
}