基础穷举搜索（Basic Complete Search）

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

在许多问题中（尤其是青铜级题目），只需检查解空间中的所有可能情况即可解决问题，这些情况可能是所有元素、所有元素对、所有子集或所有排列。显然，这种方法被称为穷举搜索（或暴力搜索，brute force），因为它会完整地搜索整个解空间。

最大距离（Maximum Distance）

给定平面直角坐标系中的 N 个整数点（3≤N≤5000）。请找出任意两点之间欧几里得距离（即直线长度）的平方的最大值。

Input

第一行包含一个整数 N。

第二行包含 N 个整数，代表这些点的 xx 坐标：x₁, x₂, …, x_N（−1000≤x_i≤1000）。

第三行包含 N 个整数，代表这些点的 yy 坐标：y₁, y₂, …, y_N（−1000≤y_i≤1000）。

Output

输出一个整数，即任意两点之间欧几里得距离的平方的最大值。

Example

Input

3
321 -15 -525
404 373 990

Output

解决方案 - 最大距离（Maximum Distance）

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

用变量max_squared记录当前最大的距离平方。

C++

#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;                   // stores the current maximum
	for (int i = 0; i < n; i++) {          // for each first point
		for (int j = i + 1; j < n; j++) {  // and each second point
			int dx = x[i] - x[j];
			int dy = y[i] - y[j];
			int square = dx * dx + dy * dy;

			/*
			 * if the square of the distance between the two points is
			 * greater than our current maximum, then update the maximum
			 */
			max_squared = max(max_squared, square);
		}
	}

	cout << max_squared << endl;
}

几点说明：

1. 由于我们要遍历所有点对，j循环从j = i+1开始，这样可以确保点i和点j不会是同一个点，并且每一对点只会被统计一次。在本题中，是否重复统计点对或是否允许i和j为同一个点并不影响结果，但在其他需要计数而非求最大值的问题中，必须注意避免重复计数。

2. 本题要求计算任意两点之间欧几里得距离的平方的最大值。有些学生可能会倾向于用整数变量存储最大距离，最后输出时再平方。但问题在于，虽然两个整数坐标点之间距离的平方一定是整数，但距离本身不一定是整数。如果将非整数值存入整数变量，会导致小数部分被截断，从而产生错误。

C++（用浮点型变量存储最大距离的正确实现）

#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;                   // stores the current maximum
	for (int i = 0; i < n; i++) {          // for each first point
		for (int j = i + 1; j < n; j++) {  // and each second point
			int dx = x[i] - x[j];
			int dy = y[i] - y[j];
			int square = dx * dx + dy * dy;

			/*
			 * if the square of the distance between the two points is
			 * greater than our current maximum, then update the maximum
			 */
			max_squared = max(max_squared, square);
		}
	}

	cout << max_squared << endl;
}

但该实现仍会在以下测试用例中失败（输出结果为12，正确答案应为13）：

2
0 3
2 0

此时只需进行四舍五入（(int) round(pow(max_dist, 2))）即可修正，但关键启示是：尽可能使用整数类型进行计算。

但该实现仍会在以下测试用例中失败（输出结果为12，正确答案应为13）：

2
0 3
2 0

此时只需进行四舍五入（(int) Math.round(Math.pow(maxDist, 2))）即可修正，但关键启示是：尽可能使用整数类型进行计算。

题目

	链接	来源	题目名称	难度	标签
	http://oj.oldmoon.cn/p/U1516FB1	青铜级	牛奶桶（Milk Pails）	简单	显示标签：穷举搜索
		青铜级	钻石收集者（Diamond Collector）	简单	显示标签：穷举搜索
		青铜级	雏菊花链（Daisy Chains）	简单	显示标签：穷举搜索
		青铜级	数说谎者（Counting Liars）	中等	显示标签：穷举搜索、排序
*	http://oj.oldmoon.cn/p/U1920DB1	青铜级	奶牛体操（Cow Gymnastics）	中等	显示标签：穷举搜索
*		青铜级	牛基因组（Bovine Genomics）	中等	显示标签：穷举搜索
		青铜级	三角形（Triangles）	中等	显示标签：穷举搜索
		青铜级	救生员（Lifeguards）	中等	显示标签：穷举搜索
*	http://oj.oldmoon.cn/p/U1617FB2	青铜级	牛为什么过马路 II（Why Did the Cow Cross the Road II）	中等	显示标签：穷举搜索
		青铜级	猜动物（Guess the Animal）	困难	显示标签：穷举搜索
*	http://oj.oldmoon.cn/p/U1617OS2	白银级	牛基因组（Bovine Genomics）	困难	显示标签：穷举搜索
*	http://oj.oldmoon.cn/p/U1516FB3	青铜级	负载均衡（Load Balancing）	困难	显示标签：穷举搜索
*	http://oj.oldmoon.cn/p/U2122FB1	青铜级	课堂睡觉（Sleeping in Class）	困难	显示标签：穷举搜索
*	http://oj.oldmoon.cn/p/U2425JB3	青铜级	奶牛体检（Cow Checkups）	困难	显示标签：穷举搜索
	http://oj.oldmoon.cn/p/U1516DB3	青铜级	受污染的牛奶（Contaminated Milk）	极难	显示标签：穷举搜索
*		青铜级	奶牛接触追踪（Cowntact Tracing）	极难	显示标签：穷举搜索
		青铜级	瓷器店里的公牛（Bull in a China Shop）	极难	显示标签：穷举搜索
		白银级	负载均衡（Load Balancing）	极难	显示标签：穷举搜索
		青铜级	哞语言（Moo Language）	极难	显示标签：穷举搜索