题意：给定一个立体直角坐标系上的(n)个整点，求一个整点满足到这(n)个整点的曼哈顿距离的最大值最小。
首先显然二分。
那么，要解若干方程：|x-Xi|+|y-Yi|+|z-Zi|<=m。
遇到绝对值方程/不等式，我们有2种方式：
- 零点分段
- 拆方程：|a|拆成a，-a。
考虑第二种方法。
会得到8个不等式。把x系数都调为1，剩余4个不等式。
由于是4个不等式，3个变量，因此一定有一个式子能被其它式子表出。
把其他式子换元为abc，那么我们可以知道abc的范围，以及a+b+c的范围。
同时，由于要求整点，还要满足abc奇偶性相同。
枚举除以2的余数，进行计算即可。
细节很多。
代码：
#include <stdio.h>
#define ll long long
#define inf 9e18
ll mabs(ll s)
{
return s>=0?s:-s;
}
bool solve(ll L[3],ll R[3],ll HL,ll HR,ll A[3])
{
if(HL>HR)return false;
ll hl=0,hr=0;
for(int i=0;i<3;i++)
{
if(L[i]>R[i])return false;
hl+=L[i],hr+=R[i],A[i]=L[i];
}
if(hl>HR||HL>hr)
return false;
if(hl>=HL)
return true;
ll sy=HL-hl;
for(int i=0;i<3;i++)
{
ll z=R[i]-L[i];
if(sy<z)z=sy;
A[i]+=z;sy-=z;
}
return true;
}
void div2(ll &L,ll &R)
{
ll l=L/2,r=R/2;
if(r*2>R)r-=1;
if(l*2<L)l+=1;
L=l;R=r;
}
ll X[100010],Y[100010],Z[100010],S[2][2][2],L[2][2],R[2][2];int n;
bool check(ll m,ll A[3])
{
for(int a=0;a<2;a++)
for(int b=0;b<2;b++)
for(int c=0;c<2;c++)
S[a][b][c]=inf;
for(int i=1;i<=n;i++)
{
for(int a=0;a<2;a++)
{
for(int b=0;b<2;b++)
{
for(int c=0;c<2;c++)
{
ll t=m+X[i]*(a*2-1)+Y[i]*(b*2-1)+Z[i]*(c*2-1);
if(t<S[a][b][c])S[a][b][c]=t;
}
}
}
}
for(int a=0;a<2;a++)
{
for(int b=0;b<2;b++)
{
L[a][b]=-S[0][a^1][b^1],R[a][b]=S[1][a][b];
if(L[a][b]>R[a][b])return false;
}
}
ll l[3]={-R[1][1],L[1][0],L[0][1]},r[3]={-L[1][1],R[1][0],R[0][1]};
for(int k=0;k<2;k++)
{
ll zl[3],zr[3],hl=L[0][0]-k*3,hr=R[0][0]-k*3;
for(int i=0;i<3;i++)
{
zl[i]=l[i]-k;zr[i]=r[i]-k;
div2(zl[i],zr[i]);
}
div2(hl,hr);ll jg[3];
if(solve(zl,zr,hl,hr,jg))
{
ll a=jg[0]*2+k,b=jg[1]*2+k,c=jg[2]*2+k;
A[0]=(b+c)/2;A[1]=(-a-c)/2;A[2]=(-a-b)/2;
return true;
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ll l=0,r=0,jg[3];
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&X[i],&Y[i],&Z[i]);
ll t=mabs(X[i])+mabs(Y[i])+mabs(Z[i]);
if(t>r)r=t;
}
while(l<r)
{
ll m=(l+r)>>1;
if(check(m,jg))
r=m;
else
l=m+1;
}
check(l,jg);
printf("%lld %lld %lld
",jg[0],jg[1],jg[2]);
}
return 0;
}