自动搬运

查看原文

来自洛谷，原作者为

	the_Short_Path sum[i]=sum[i-1]+a[i]

搬运于2025-08-24 21:18:08，当前版本为作者最后更新于2025-04-02 21:32:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

一道水题

• $op=1$ 时，暴力枚举每对点，数据范围比较水。
• $op=2$ 时，分别计算每个点 $i$ 的 $x_i$ 和 $y_i$ 的和与差的最大值和最小值，再将两个最大值和最小值的差取较大值，原因见证明。

证明：

对于两个点 $(x_i,y_i)$ 和 $(x_j,y_j)$，其曼哈顿距离有：

1. $(x_i + y_i) - (x_j + y_j)$
2. $(x_i + y_i) - (x_j - y_j)$
3. $-(x_i + y_i) + (x_j + y_j)$
4. $-(x_i + y_i) + (x_j - y_j)$

所以可以枚举所有的 $(x_i + y_i)$ 和 $(x_i - y_i)$，分别求其 $\max$ 和 $\min$，差的较大值即为曼哈顿距离最大值。

Code

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const long long maxn = 1e6 + 5;
long long n, op, ans, x[maxn], y[maxn];
// 十年 OI 一场空，不开 long long 见祖宗
signed main() {
	cin >> n >> op;
	for (long long i = 1; i <= n; i++) cin >> x[i] >> y[i];
	if (op == 1) {
		for (long long i = 1; i <= n; i++) 
			for (long long j = i + 1; j <= n; j++) 
				ans = max(ans, (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
	} else {
        long long mx1 = 0, mx2 = 0, mn1 = inf, mn2 = inf;
        for (long long i = 1; i <= n; i++) {
            mx1 = max(mx1, x[i] - y[i]);
            mx2 = max(mx2, x[i] + y[i]);
            mn1 = min(mn1, x[i] - y[i]);
            mn2 = min(mn2, x[i] + y[i]);
        } // 计算每个点 i 的 xi 和 yi 的和与差的最大值和最小值
        ans = max(mx1 - mn1 , mx2 - mn2);
    }
    cout << ans << endl;
	return 0;
} 

其实很简单的，就是需要懂一些技巧。