题解 CF685C【Optimal Point】

· · 题解

CF685C Optimal Point解题报告：

更好的阅读体验

题意

给定 n 个立体三维坐标系的整点（坐标范围 [-10^{18},10^{18}] ），求一个点使得其与所有点的曼哈顿距离最大值最小。（ 1\leqslant n\leqslant 10^5 ）

分析

优美的胖题。

首先求最大值最小就可以知道要二分这个距离最大值。

考虑怎么 check 这个距离 mid ，发现这等价于解这个方程组的解（其中 x_0,y_0,z_0 为未知数）：

\begin{cases}|x_1-x_0|+|y_1-y_0|+|z_1-z_0|\leqslant mid\\|x_2-x_0|+|y_2-y_0|+|z_2-z_0|\leqslant mid\\\cdots\\|x_n-x_0|+|y_n-y_0|+|z_n-z_0|\leqslant mid\end{cases}

发现这个绝对值很难拆，但由于 \max\{a-b,b-a\}=|a-b| ，所以每个不等式可以等价为：

\begin{cases}x_i-x_0+y_i-y_0+z_i-z_0\leqslant mid\\x_0-x_i+y_i-y_0+z_i-z_0\leqslant mid\\x_i-x_0+y_0-y_i+z_i-z_0\leqslant mid\\x_0-x_i+y_0-y_i+z_i-z_0\leqslant mid\\x_i-x_0+y_i-y_0+z_0-z_i\leqslant mid\\x_0-x_i+y_i-y_0+z_0-z_i\leqslant mid\\x_i-x_0+y_0-y_i+z_0-z_i\leqslant mid\\x_0-x_i+y_0-y_i+z_0-z_i\leqslant mid\end{cases}

然后不难发现这个不等式可以化作：

\begin{cases}x_i+y_i+z_i-mid\leqslant x_0+y_0+z_0\leqslant x_i+y_i+z_i+mid\\-x_i+y_i+z_i-mid\leqslant -x_0+y_0+z_0\leqslant -x_i+y_i+z_i+mid\\x_i-y_i+z_i-mid\leqslant x_0-y_0+z_0\leqslant x_i-y_i+z_i+mid\\x_i+y_i-z_i-mid\leqslant x_0+y_0-z_0\leqslant x_i+y_i-z_i+mid\end{cases}

设 al,bl,cl,dl 为前四个式子的最大值， ar,br,cr,dr 为后四个式子的最小值，， a=-x_0+y_0+z_0,b=x_0-y_0+z_0,c=x_0+y_0-z_0 ，那么等价于：

\begin{cases}al\leqslant a+b+c\leqslant ar\\bl\leqslant a\leqslant br\\cl\leqslant b\leqslant cr\\dl\leqslant c\leqslant dr\end{cases}

由于 x_0=\frac{b+c}{2},y_0=\frac{a+c}{2},z_0=\frac{a+b}{2} ，且它们都是整数，所以还有 a\equiv b\equiv c\pmod 2 。

此时套路地枚举 a,b,c 的最后一个二进制位 t\in\{0,1\} 再处理一下边界，那么模 2 相同的限制就没了，最后不难用调整法算出一个答案。

时间复杂度： O(n\log v) 。

代码

#include<stdio.h>
#include<iostream>
#define inf 6000000000000000000
using namespace std;
const int maxn=100005;
int T,n;
long long ansx,ansy,ansz;
long long x[maxn],y[maxn],z[maxn];
inline long long ceil(long long x){
    return x>=0? (x+1)/2ll:-((-x)/2ll);
}
inline long long floor(long long x){
    return x>=0? x/2ll:-((-x+1)/2ll);
}
int check(long long mid){
    long long al=-inf,bl=-inf,cl=-inf,dl=-inf,ar=inf,br=inf,cr=inf,dr=inf;
    //al<=a+b+c<=ar,bl<=a<=br,cl<=b<=cr,dl<=c<=dr
    for(int i=1;i<=n;i++){
        al=max(al,x[i]+y[i]+z[i]-mid),ar=min(ar,x[i]+y[i]+z[i]+mid);
        bl=max(bl,-x[i]+y[i]+z[i]-mid),br=min(br,-x[i]+y[i]+z[i]+mid);
        cl=max(cl,x[i]-y[i]+z[i]-mid),cr=min(cr,x[i]-y[i]+z[i]+mid);
        dl=max(dl,x[i]+y[i]-z[i]-mid),dr=min(dr,x[i]+y[i]-z[i]+mid);
    }
    for(int t=0;t<=1;t++){
        long long wl=ceil(al-3*t),wr=floor(ar-3*t);
        long long xl=ceil(bl-t),xr=floor(br-t);
        long long yl=ceil(cl-t),yr=floor(cr-t);
        long long zl=ceil(dl-t),zr=floor(dr-t);
        if(wl<=wr&&xl<=xr&&yl<=yr&&zl<=zr&&xl+yl+zl<=wr&&xr+yr+zr>=wl){
            long long x=xl,y=yl,z=zl,up=max(0ll,wl-xl-yl-zl);
            x+=min(up,xr-xl),up-=min(up,xr-xl);
            y+=min(up,yr-yl),up-=min(up,yr-yl);
            z+=min(up,zr-zl),up-=min(up,zr-zl);
            x=((x<<1)|t),y=((y<<1)|t),z=((z<<1)|t);
            ansx=(y+z)>>1,ansy=(x+z)>>1,ansz=(x+y)>>1;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
        long long L=-1,R=inf+1;
        while(L+1<R){
            long long mid=L+(R-L)/2ll;
            if(check(mid))
                R=mid;
            else L=mid;
        }
        check(R);
        printf("%lld %lld %lld\n",ansx,ansy,ansz);
    }
    return 0;
}

整场比赛的题解