- 给定三维空间内(n)个整点，求一个整点到它们曼哈顿距离的最大值最小。
- 数据组数(le10^5)，(sum nle10^5)
二分答案+构造
考虑要最小化最大值，容易想到二分答案(d)，那么就是要判断是否存在一个整点((X,Y,Z))满足：
[forall iin[1,n],|X-x_i|+|Y-y_i|+|Z-z_i|le d
]
众所周知，(|x|=max{x,-x})，所以(|x|le yLeftrightarrow xle ywedge -xle y)。
也就是说，上面的式子可以被我们暴拆成八个式子，把(X,Y,Z)单独放一边，(x_i,y_i,z_i)和(d)放到另一边，就可以计算出(X+Y+Z)，(X+Y-Z)，(X+Z-Y)，(Y+Z-X)四者的取值范围。
直接做仍旧是比较棘手的，发现(X+Y+Z)恰好等于后面三项之和，因此令(A=X+Y-Z)，(B=X+Z-Y)，(C=Y+Z-X)，只要解出(A,B,C)的值就能还原出(X=frac{A+B}2)，(Y=frac{A+C}2)，(Z=frac{B+C}2)。
但还要保证解得的(X,Y,Z)是整数，这充要于(A,B,C)奇偶性相同。
因此我们不妨枚举(i=A\% 2)，则(A=2A'+i)，(B=2B'+i)，(C=2C'+i)，则我们可以通过原本的范围计算出(A'+B'+C',A',B',C')的范围。
再要判是否存在解就非常简单了，首先如果某一项的取值范围为空（左边界大于右边界）显然无解。
否则，(A'+B'+C')实际的取值范围应该是(A',B',C')最小值之和到最大值之和（中间的所有整值都能取到）。
故将(A'+B'+C')限制的取值范围与此比较，如果无交说明无解，否则有解。
而要构造一组解也是很简单的，先让(A',B',C')全取最小值，然后依次枚举每个数往大调整即可。
代码：(O(sum nlogV))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define LL long long
#define INF (LL)4e18
using namespace std;
int n;LL x[N+5],y[N+5],z[N+5];
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define D isdigit(oc=tc())
int ff;char oc,FI[FS],*FA=FI,*FB=FI;
Tp I void read(Ty& x) {x=0,ff=1;W(!D) ff=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),D);x*=ff;}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
I bool Check(Con LL& d,CI op=0)//验证
{
LL l=-INF,r=INF,la=-INF,ra=INF,lb=-INF,rb=INF,lc=-INF,rc=INF;
RI i;for(i=1;i<=n;++i)
l=max(l,x[i]+y[i]+z[i]-d),r=min(r,x[i]+y[i]+z[i]+d),//求X+Y+Z范围
la=max(la,x[i]+y[i]-z[i]-d),ra=min(ra,x[i]+y[i]-z[i]+d),//求X+Y-Z范围
lb=max(lb,x[i]+z[i]-y[i]-d),rb=min(rb,x[i]+z[i]-y[i]+d),//求X+Z-Y范围
lc=max(lc,y[i]+z[i]-x[i]-d),rc=min(rc,y[i]+z[i]-x[i]+d);//求Y+Z-X范围
LL A,B,C,L,R,LA,RA,LB,RB,LC,RC;for(i=0;i<=1;++i)//枚举A,B,C的奇偶性
{
L=l-3*i+1>>1,R=r-3*i>>1,LA=la-i+1>>1,RA=ra-i>>1,LB=lb-i+1>>1,RB=rb-i>>1,LC=lc-i+1>>1,RC=rc-i>>1;//求出新范围
if(L>R||LA>RA||LB>RB||LC>RC||LA+LB+LC>R||RA+RB+RC<L) continue;//如果存在值域为空或两值域区间无交则无解
(A=LA)+(B=LB)+(C=LC)<L&&(A+=min(RA-LA,R-A-B-C))+B+C<L&&A+(B+=min(RB-LB,R-A-B-C))+C<L&&(C+=min(RC-LC,R-A-B-C));//先全取最小值，依次往大调整
return op&&((A<<=1)|=i,(B<<=1)|=i,(C<<=1)|=i,printf("%lld %lld %lld
",A+B>>1,A+C>>1,B+C>>1)),true;//还原A,B,C，输出构造方案
}return false;
}
int main()
{
RI Tt,i;LL l,r,mid;read(Tt);W(Tt--)
{
for(read(n),i=1;i<=n;++i) read(x[i],y[i],z[i]);
l=0,r=INF,mid;W(l^r) Check(mid=l+r-1>>1)?r=mid:l=mid+1;Check(r,1);//二分答案
}return 0;
}