CF685C Optimal Point 题解

CF685C Optimal Point

题意

• 立体直角坐标系中有 $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)$。

说句题外话，代码不太会写，偷偷看一眼兔兔的，发现他偷偷看了题解代码（

代码

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;
}