专栏文章

题解：B4253 [科大国创杯小学组 2024] 几何

tthe_Short_Path
B4253题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipqe242
此快照首次捕获于
2025/12/03 16:14
3 个月前
此快照最后确认于
2025/12/03 16:14
3 个月前
查看原文
题目传送门
一道水题
  • op=1op=1 时，暴力枚举每对点，数据范围比较水。
  • op=2op=2 时，分别计算每个点 ii 的 xix_i 和 yiy_i 的和与差的最大值和最小值，再将两个最大值和最小值的差取较大值，原因见证明。
证明：
对于两个点 (xi,yi)(x_i,y_i) 和 (xj,yj)(x_j,y_j)，其曼哈顿距离有：
  1. (xi+yi)−(xj+yj)(x_i + y_i) - (x_j + y_j)
  2. (xi+yi)−(xj−yj)(x_i + y_i) - (x_j - y_j)
  3. −(xi+yi)+(xj+yj)-(x_i + y_i) + (x_j + y_j)
  4. −(xi+yi)+(xj−yj)-(x_i + y_i) + (x_j - y_j)
所以可以枚举所有的 (xi+yi)(x_i + y_i) 和 (xi−yi)(x_i - y_i)，分别求其 max⁡\max 和 min⁡\min，差的较大值即为曼哈顿距离最大值。

Code

CPP
#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;
}
其实很简单的，就是需要懂一些技巧。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...