涉及遍历整个解空间的问题

资料-resources

6 - Complete Search

在很多问题中（尤其是在 USACO Bronze 级别），只需检查解空间中的所有可能情况就足够了，比如所有元素、所有元素对、所有子集，或者所有排列。

毫不奇怪，这种方法被称为完全搜索（complete search）或暴力搜索（brute force），因为它会彻底遍历整个解空间。

问题-problem

Maximum Distance

Solution - Maximum Distance

我们可以遍历每一对点，并通过对欧几里得距离公式平方来计算它们之间的距离平方：

$${\text{distance}}^2\left[(x_1,y_1),(x_2,y_2)\right]=(x_2-x_1{)}^2+(y_2-y_1{)}^2$$

将当前的最大距离平方值保存在变量 max_squared 中。

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;vector<int> x(n), y(n);for (int &t : x) { cin >> t; }for (int &t : y) { cin >> t; }int max_squared = 0;                   // 存储当前最大距离平方for (int i = 0; i < n; i++) {          // 遍历每个第一个点for (int j = i + 1; j < n; j++) {  // 遍历每个第二个点（避免重复和自比较）int dx = x[i] - x[j];int dy = y[i] - y[j];int square = dx * dx + dy * dy;/** 如果两点距离的平方大于当前最大值，则更新最大值*/max_squared = max(max_squared, square);}}cout << max_squared << endl;
}

由于我们要遍历所有点对，因此让内层循环从 $j=i+1$ 开始，确保点 $i$ 和点 $j$ 永远不会是同一个点。另外，这样还能保证每一对点只被计算一次。

在这道题中，即使重复计算点对或允许 $i=j$ 也不会影响最终结果（求最大距离），但在其他需要计数的问题中，避免重复计数非常重要。

题目要求输出的是任意两点之间最大欧几里得距离的平方。

有些同学可能想先用整数变量存储最大距离，然后最后再对结果进行平方。

但这里的问题是，两个整数点之间的距离平方一定是整数，但距离本身不一定是整数（可能是无理数或小数）。因此，如果先存储距离（非整数）到整数变量，会导致小数部分被截断，造成错误。

下面的解决方案使用浮点型变量来正确存储最大距离。

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;vector<int> x(n), y(n);for (int &t : x) { cin >> t; }for (int &t : y) { cin >> t; }double max_dist = 0;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {int dx = x[i] - x[j];int dy = y[i] - y[j];int square = dx * dx + dy * dy;max_dist = max(max_dist, sqrt(square));}}cout << (int)pow(max_dist, 2) << endl;
}

但是，这段代码在以下测试用例上仍然会失败（它输出了 $12$，而正确答案是 $13$）：

2
0 3
2 0

原因是浮点数计算的舍入误差导致的。虽然使用 (int) round(pow(max_dist, 2)) 进行四舍五入可以解决这个问题，但最重要的结论是：尽可能使用整数计算，避免浮点数误差。