题解 CF685C 【Optimal Point】
xht
2020-03-10 15:28:37
> [CF685C Optimal Point](https://codeforces.com/contest/685/problem/C)
## 题意
- 立体直角坐标系中有 $n$ 个整点。
- 求一个整点满足到这 $n$ 个整点的曼哈顿距离的最大值最小。
- $n \le 10^5$。
## 题解
显然先二分答案。
考虑如何 check，假设此时二分到的值为 $d$。
则我们可以得到 $n$ 个限制 $|x - x_i| + |y - y_i| + |z - z_i| \le d$。
不妨设 $x_i = y_i = z_i = 0$，我们考虑 $|x| + |y| + |z| \le d$ 的情况。
枚举每个绝对值取正取负，我们可以列出 $2^3 = 8$ 个不等式。
合并这 $8n$ 个不等式，最终会得到一个不等式组：
$$\begin{cases}l \leq x+y+z \leq r \\lx \leq-x+y+z \leq rx \\ly \leq x-y+z \leq ry \\lz \leq x+y-z \leq rz\end{cases}$$
设 $a=-x+y+z$，$b=x-y+z$，$c=x+y-z$，则 $x=\frac{b+c}{2}$，$y=\frac{a+c}{2}$，$z=\frac{a+b}{2}$，且 $x+y+z = a+b+c$，且 $a,b,c$ 奇偶性相同。
令 $a = 2a^{\prime} + r$，$b = 2b^{\prime} + r$，$c = 2c^{\prime} + r$，其中 $r \in [0,1]$，则我们最终得到的不等式组为：
$$\begin{cases}l^{\prime} \leq a^{\prime}+b^{\prime}+c^{\prime} \leq r^{\prime} \\lx^{\prime} \leq a^{\prime} \leq rx^{\prime} \\ly^{\prime} \leq b^{\prime} \leq ry^{\prime} \\lz^{\prime} \leq c^{\prime} \leq rz^{\prime}\end{cases}$$
我们要求出这个不等式组的一组解。
先贪心的设 $a^{\prime} = lx^{\prime}$，$b^{\prime} = ly^{\prime}$，$c^{\prime} = lz^{\prime}$，若不满足 $l^{\prime} \leq a^{\prime}+b^{\prime}+c^{\prime} \leq r^{\prime}$，则一个一个调大 $a^{\prime}, b^{\prime}, c^{\prime}$。
这样我们就可以 $\mathcal O(n)$ check 并构造了，时间复杂度 $\mathcal O(n \log w)$。
说句题外话，代码不太会写，偷偷看一眼兔兔的，发现他偷偷看了题解代码（
## 代码
```cpp
const int N = 1e5 + 7;
const ll inf = 4e18;
#define Max(a, b) (a = a > b ? a : b)
#define Min(a, b) (a = a < b ? a : b)
int n;
ll x[N], y[N], z[N], X, Y, Z, mx, mxx, mxy, mxz, mn, mnx, mny, mnz;
inline bool pd(ll o) {
mx = mxx = mxy = mxz = inf, mn = mnx = mny = mnz = -inf;
for (int i = 1; i <= n; i++)
Min(mx, o + x[i] + y[i] + z[i]),
Min(mxx, o - x[i] + y[i] + z[i]),
Min(mxy, o + x[i] - y[i] + z[i]),
Min(mxz, o + x[i] + y[i] - z[i]),
Max(mn, -o + x[i] + y[i] + z[i]),
Max(mnx, -o - x[i] + y[i] + z[i]),
Max(mny, -o + x[i] - y[i] + z[i]),
Max(mnz, -o + x[i] + y[i] - z[i]);
for (int i = 0; i < 2; i++) {
ll l = mn + ((mn & 1) ^ i), r = mx - ((mx & 1) ^ i);
ll lx = mnx + ((mnx & 1) ^ i), rx = mxx - ((mxx & 1) ^ i);
ll ly = mny + ((mny & 1) ^ i), ry = mxy - ((mxy & 1) ^ i);
ll lz = mnz + ((mnz & 1) ^ i), rz = mxz - ((mxz & 1) ^ i);
if (l > r || lx > rx || ly > ry || lz > rz) continue;
ll a = lx, b = ly, c = lz;
if (a + b + c > r) continue;
if (a + b + c < l) a = rx < l - b - c ? rx : l - b - c;
if (a + b + c < l) b = ry < l - a - c ? ry : l - a - c;
if (a + b + c < l) c = rz < l - a - b ? rz : l - a - b;
if (a + b + c < l) continue;
return X = (b + c) >> 1, Y = (a + c) >> 1, Z = (a + b) >> 1, 1;
}
return 0;
}
inline void solve() {
rd(n);
for (int i = 1; i <= n; i++) rd(x[i]), rd(y[i]), rd(z[i]);
ll l = 0, r = inf;
while (l <= r) {
ll mid = (l + r) >> 1;
if (pd(mid)) r = mid - 1;
else l = mid + 1;
}
print(X, ' '), print(Y, ' '), print(Z);
}
int main() {
int T;
rd(T);
while (T--) solve();
return 0;
}
```