涉及遍歷整個解空間的問題

資料-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)) 進行四舍五入可以解決這個問題，但最重要的結論是：盡可能使用整數計算，避免浮點數誤差。