目录
@description@
给定若干个三维空间的点 (xi, yi, zi)，求一个坐标都为整数的点 P，使得 P 到这些点的最大曼哈顿距离最小。
@solution@
显然三分套三分套三分。
看到最大值，把绝对值 |x| 拆成 max(x, -x)。接着二分最大距离 d，则 max(…) ≤ d。
因此得到如下不等式组：
\[\begin{cases}
l_1 \leq x + y + z \leq r_1 \\
l_2 \leq x + y – z \leq r_2 \\
l_3 \leq x – y + z \leq r_3 \\
l_4 \leq – x + y + z \leq r_4 \\
\end{cases}
\]
仿照二维情况将曼哈顿距离转切比雪夫距离的方式，作代换 \(a = x + y – z, b = x – y + z, c = – x + y + z\)。
则有：\(x = \frac{a + b}{2}, y = \frac{a + c}{2}, z = \frac{b + c}{2}, x + y + z = a + b + c\)。
当 \(x, y, z\) 都是整数时，\(a, b, c\) 同奇同偶。不妨先枚举奇偶性，则可把原不等式变形为如下形式：
\[\begin{cases}
l_1′ \leq a’ + b’ + c’ \leq r_1′ \\
l_2′ \leq a’ \leq r_2′ \\
l_3′ \leq b’ \leq r_3′ \\
l_4′ \leq c’ \leq r_4′ \\
\end{cases}
\]
这样做的好处是，我们只留下了一个 \(a’, b’, c’\) 互相制约的不等式。
剩下的只需要贪心地把 \(a’, b’, c’\) 先设置为最小值，然后往上调整即可。时间复杂度 \(O(n\log A)\)。
@accepted code@
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;typedef long long ll;const ll INF = ll(3E18);
const int dx[4] = {1, 1, 1, -1};
const int dy[4] = {1, 1, -1, 1};
const int dz[4] = {1, -1, 1, 1};ll le[4], ri[4];
ll a1, b1, c1;
bool get() {
for(int i=0;i<4;i++)
if( le[i] > ri[i] ) return false;a1 = le[1], b1 = le[2], c1 = le[3];
if( a1 + b1 + c1 > ri[0] ) return false;
else {
if( a1 + b1 + c1 < le[0] ) {
if( ri[1] + b1 + c1 >= le[0] ) {
a1 = le[0] - b1 - c1;
return true;
} else {
a1 = ri[1];
if( a1 + ri[2] + c1 >= le[0] ) {
b1 = le[0] - a1 - c1;
return true;
} else {
b1 = ri[2];
if( a1 + b1 + ri[3] >= le[0] ) {
c1 = le[0] - a1 - b1;
return true;
} else return false;
}
}
} else return true;
}
}ll lb[4], ub[4];
ll ansx, ansy, ansz;
bool check(ll d) {
for(int o=0;o<=1;o++) {
le[0] = (lb[0] - d) - 3*o, ri[0] = (ub[0] + d) - 3*o;
for(int i=1;i<4;i++) le[i] = (lb[i] - d) - o, ri[i] = (ub[i] + d) - o;
for(int i=0;i<4;i++) le[i] = ceil((long double)le[i] / 2), ri[i] = floor((long double)ri[i] / 2);
if( get() ) {
ll a = 2*a1 + o, b = 2*b1 + o, c = 2*c1 + o;
ansx = (a + b) / 2, ansy = (a + c) / 2, ansz = (b + c) / 2;
return true;
}
}
return false;
}
void solve() {
int n; scanf("%d", &n);
for(int i=0;i<4;i++) lb[i] = -INF, ub[i] = INF;
for(int i=1;i<=n;i++) {
ll x, y, z; scanf("%lld%lld%lld", &x, &y, &z);
for(int j=0;j<4;j++) {
lb[j] = max(lb[j], dx[j]*x + dy[j]*y + dz[j]*z);
ub[j] = min(ub[j], dx[j]*x + dy[j]*y + dz[j]*z);
}
}ll l = 0, r = INF;
while( l < r ) {
ll m = (l + r) >> 1;
if( check(m) ) r = m;
else l = m + 1;
}
check(r); printf("%lld %lld %lld\n", ansx, ansy, ansz);
}int main() {
int T; scanf("%d", &T);
while( T-- ) solve();
}
@details@
一开始本来想转类切比雪夫距离结果发现好像二维三维不一样。
然后尝试从立体几何入手想象，发现我完全没学过立几。
果然这是一道数学题啊。数学题好难。
