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 − x_i| + |y − y_i| + |z − z_i| ≤ 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);
    }
}