# johnchen902's Blog

## Optimal Point

### Problem

Find an integer point minimizing the maximum Manhattan distance to each given integer points in 3-space.

### Solution

As an optimization problem, if its decision version can be solved, we can binary search the answer. We'll need some elementary math.

Obviously the decision version is ∃x,y,z : ∀i : |x − xi| + |y − yi| + |z − zi| ≤ k $$\exists x,y,z:\forall i:\lvert x-x_i\rvert+\lvert y-y_i\rvert+\lvert z-z_i\rvert\le k$$ Expanding the formula, we can get: a ≤ x + y + z ≤ b
c ≤ x + y − z ≤ d
e ≤ x − y + z ≤ f
g ≤ x − y − z ≤ h
\left\{\begin{align} a & \le x + y + z \le b \\ c & \le x + y - z \le d \\ e & \le x - y + z \le f \\ g & \le x - y - z \le h \end{align}\right. Or equivalently, p = max(a − x, x − h) ≤ y + z ≤ min(b − x, x − g) = q
r = max(c − x, x − f) ≤ y − z ≤ min(d − x, x − e) = s
\left\{\begin{align} p = \max(a - x, x - h) & \le y + z \le \min(b - x, x - g) = q\\ r = \max(c - x, x - f) & \le y - z \le \min(d - x, x - e) = s \end{align}\right. And it has an integer solution if and only if p ≤ q ∧ r ≤ s ∧ (p < q ∨ r < s ∨ (p + r) is even) $$p \le q \land r \le s \land (p \lt q \lor r \lt s \lor (p + r) \text{ is even})$$ Not willing to expand the expression above, I determined that it is sufficient to test the following x: ⌊(a + g) / 2⌋, ⌊(a + g) / 2⌋ + 1, ⌊(c + e) / 2⌋, ⌊(c + e) / 2⌋ + 1, ⌊(d + f) / 2⌋ $$\left\{ \left\lfloor\frac{a + g}{2}\right\rfloor, \left\lfloor\frac{a + g}{2}\right\rfloor + 1, \left\lfloor\frac{c + e}{2}\right\rfloor, \left\lfloor\frac{c + e}{2}\right\rfloor + 1, \left\lfloor\frac{d + f}{2}\right\rfloor \right\}$$

One tricky thing is to implement the floor function, as integer division rounds toward zero on most machine, and we're already on the edge of integer overflow.

### Source Code

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;

/**
* returns (a + b) / 2, rounding toward negative infinity
*/
ll avg(ll a, ll b) {
return a / 2 + b / 2 + (a % 2 + b % 2 + 2) / 2 - 1;
}

/**
* Solve a <= x + y <= b
*       c <= x - y <= d
*/
bool solve(ll a, ll b, ll c, ll d, ll &x, ll &y) {
if(a > b || c > d || (a == b && c == d && ((a ^ c) & 1)))
return false;
x = avg(a, c + 1);
y = max(a - x, x - d);
return true;
}

/**
* Solve a <= x + y + z <= b
*       c <= x + y - z <= d
*       e <= x - y + z <= f
*       g <= x - y - z <= h
*/
bool solve(ll a, ll b, ll c, ll d,
ll e, ll f, ll g, ll h,
ll &x, ll &y, ll &z) {
if(a > b || c > d || e > f || g > h)
return false;
const ll testx[] = {
avg(c, e),
avg(c, e) + 1,
avg(a, g),
avg(a, g) + 1,
avg(d, f),
};
for(ll xx : testx) {
x = xx;
if(solve(max(a - x, x - h), min(b - x, x - g),
max(c - x, x - f), min(d - x, x - e), y, z))
return true;
}
return false;
}

constexpr ll maxx = 1000000000000000000LL;
ll xi[100000], yi[100000], zi[100000];

bool feasible(int n, ll k, ll &x, ll &y, ll &z) {
ll a, b, c, d, e, f, g, h;
a = c = e = g = -3 * maxx;
b = d = f = h = +3 * maxx;
for(int i = 0; i < n; i++) {
a = max(a, xi[i] + yi[i] + zi[i] - k);
b = min(b, xi[i] + yi[i] + zi[i] + k);
c = max(c, xi[i] + yi[i] - zi[i] - k);
d = min(d, xi[i] + yi[i] - zi[i] + k);
e = max(e, xi[i] - yi[i] + zi[i] - k);
f = min(f, xi[i] - yi[i] + zi[i] + k);
g = max(g, xi[i] - yi[i] - zi[i] - k);
h = min(h, xi[i] - yi[i] - zi[i] + k);
}
return solve(a, b, c, d, e, f, g, h, x, y, z);
}

void solve(int n) {
ll l = 0, r = 3 * maxx;
while(l < r) {
ll m = (l + r) / 2, x, y, z;
if(feasible(n, m, x, y, z))
r = m;
else
l = m + 1;
}
ll x, y, z;
feasible(n, l, x, y, z);
printf("%lld %lld %lld\n", x, y, z);
}

int main() {
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%lld %lld %lld", xi + i, yi + i, zi + i);
solve(n);
}
}