专栏文章

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

ccxlqwq
B4253题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miprn4rg
此快照首次捕获于
2025/12/03 16:49
3 个月前
此快照最后确认于
2025/12/03 16:49
3 个月前
查看原文

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

题目要求：
  1. 任意两点间欧几里得距离最大值的平方，对于两个点 (xi,yi)(x_i, y_i) 和 (xj,yj)(x_j, y_j)，欧几里得距离定义为 (xi−xj)2+(yi−yj)2\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}。
  2. 任意两点间曼哈顿距离最大值，对于两个点 (xi,yi)(x_i, y_i) 和 (xj,yj)(x_j, y_j)，曼哈顿距离定义为 ∣xi−xj∣+∣yi−yj∣|x_i - x_j| + |y_i - y_j|。
因为只用输出距离最大值的平方，所以欧几里得距离只要输出 (xi−xj)2+(yi−yj)2(x_i - x_j)^2 + (y_i - y_j)^2。

Code

CPP
ll ans = 0;
upto(i, 1, n) {
    upto(j, 1, n) {
        num[i] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
        ans = max(ans, num[i]);
    }
}
cout << ans;
接下来考虑曼哈顿距离最大值。我一开始用的是暴力，结果 TLE 了。
CPP
upto(i, 1, n) {
    upto(j, 1, n) {
        num[i] = fabs(x[i] - x[j]) + fabs(y[i] - y[j]);
        ans = max(ans, num[i]);
    }
}
		cout << ans;
通过观察数据，我们发现 1≤n≤1061\leq n \leq 10^6 ，因此 TLE 便是显而易见的。

正解

我们应当通过求极差的方式求出求平面曼哈顿最远点对。
极差是一个统计学中的概念，它表示一组数据中最大值与最小值之间的差异。用数学公式表示就是： 极差 = 最大值 - 最小值。

Code

CPP
ll maxa = LLONG_MIN, mina = LLONG_MAX;
ll maxb = LLONG_MIN, minb = LLONG_MAX;
	upto(i, 1, n) {
		maxa = max(maxa, x[i] + y[i]);
		mina = min(mina, x[i] + y[i]);
		maxb = max(maxb, x[i] - y[i]);
		minb = min(minb, x[i] - y[i]);
	}
cout << max(maxa - mina, maxb - minb);

AC Code

CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;// 1<=n<=1e6
#define maxn 10010
#define mod 1e9 + 7//998244353
#define upto(i, a, b) for (int i = a; i <= b; i++)//循环板子，拿走不谢
#define downto(i, a, b) for (int i = a; i >= b; i--)
#define rep(i, a, b) for (int i = a; i < b; i++)
typedef long long ll;//ll代替long long,节约录入时间
//using ll=long long;
//#define ll long long
template <typename T>//通用快读板子
inline void read(T &x) {
	x = 0;
	T f = 1;
	char ch = getchar();
	while (ch < 48 || ch > 57) {
		if (ch == '-')
			f = 0;
		ch = getchar();
	}
	while (ch >= 48 && ch <= 57)
		x = x * 10 + ch - 48, ch = getchar();
	if (!f)
		x = -x;
}

ll maxa = LONG_LONG_MIN, mina = LONG_LONG_MAX;//||LLONG_MAX
ll maxb = LONG_LONG_MIN, minb = LONG_LONG_MAX;
ll n, opt, x[N], y[N], num[N];

int main() {
	ios::sync_with_stdio(false);//关流
	read(n);
	read(opt);
	upto(i, 1, n) {
		read(x[i]), read(y[i]);
	}
	upto(i, 1, n) {//循环求极差
		maxa = max(maxa, x[i] + y[i]);
		mina = min(mina, x[i] + y[i]);
		maxb = max(maxb, x[i] - y[i]);
		minb = min(minb, x[i] - y[i]);
	}
	if (opt == 1) {//求欧几里得距离最大值的平方
		ll ans = 0;
		upto(i, 1, n) {
			upto(j, 1, n) {
				num[i] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
				ans = max(ans, num[i]);
			}
		}
		cout << ans;
	} else if (opt == 2) {
		cout << max(maxa - mina, maxb - minb);
	}
	return 0;
}

鸣谢

严格来说，对于求曼哈顿距离最大值，本篇题解在一定程度上参考了 Miku_QwQ 求极差的思路，感谢TA。
我们下篇题解再会！

评论

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

正在加载评论...