本文将详细探讨如何在给定半径`r`的情况下，高效地找出平面上距离原点`(0,0)`最近，且其与原点距离严格大于`r`的整数坐标`(x,y)`。我们将从数学原理出发，逐步优化算法，最终实现一个具有线性时间复杂度的解决方案，显著提升处理大半径时的性能。
问题阐述
给定一个整数半径r，我们的目标是寻找一对正整数坐标(x, y)，使得它们到原点的欧几里得距离D = sqrt(x^2 + y^2)满足两个条件：
- D > r (距离严格大于半径)
- D 是所有满足条件1的(x, y)对中最小的
为了简化搜索空间，通常假定x
初始方法及其性能瓶颈
最初的尝试可能涉及两层嵌套循环，遍历所有可能的x和y值，计算距离并跟踪最小值。例如，一个常见的朴素方法可能如下：
import java.util.Scanner;
public class DiscDistrictQuadratic {
public static void main(String[] args) {
Scanner new_scanner = new Scanner(System.in);
int radius = new_scanner.nextInt();
new_scanner.close();
double min_max_dist = Double.MAX_VALUE;
int[] new_min_pair = new int[2];
// 遍历x的范围，通常从1到radius，或根据问题特性优化
for (int i = 1; i <= radius; i++) {
// 遍历y的范围，通常从i到radius，确保y >= x
for (int j = i; j <= radius; j++) {
double new_dist = Math.sqrt(Math.pow(i, 2) + Math.pow(j, 2));
if (new_dist > radius) {
if (min_max_dist > new_dist) {
min_max_dist = new_dist;
new_min_pair[0] = i;
new_min_pair[1] = j;
}
}
}
}
System.out.println(new_min_pair[0] + " " + new_min_pair[1]);
}
}这种方法的时间复杂度为O(radius^2)，对于较小的radius（如r
优化策略：数学推导与剪枝
为了提高效率，我们需要减少内层循环的迭代次数。关键在于利用距离条件sqrt(x^2 + y^2) > r。 由于x, y, r都是正数，我们可以将其平方：x^2 + y^2 > r^2。 对于一个固定的x (即代码中的i)，我们需要找到最小的y (即代码中的j)，使得j^2 > r^2 - i^2。 这意味着j > sqrt(r^2 - i^2)。
因此，对于每个i值，j的起始值可以被精确计算出来，而不是从i开始盲目遍历。 j的最小整数值应为 floor(sqrt(r^2 - i^2)) + 1。
考虑到j也必须大于或等于i (为了避免重复和利用对称性)，j的实际起始值应为 max(i, floor(sqrt(r^2 - i^2)) + 1)。
从二次方到线性的飞跃
上述优化使得内层循环的起始点更精确，但如果仍保留内层循环并遍历到radius，复杂度仍是二次方。然而，我们寻求的是最小的距离。对于一个给定的i，我们已经找到了满足j > sqrt(r^2 - i^2)的最小整数j。这个j值将产生一个距离sqrt(i^2 + j^2)。如果存在一个j'使得j' > j，那么sqrt(i^2 + j'^2)必然大于sqrt(i^2 + j^2)。因此，对于每个i，我们只需要检查这个唯一的、最小的满足条件的j，而无需遍历所有更大的j值。
这将内层循环完全消除，从而将算法复杂度从O(radius^2)降低到O(radius)，实现线性时间复杂度。
优化后的线性时间算法实现
import java.util.Scanner;
public class DiscDistrictLinear {
public static void main(String[] args) {
Scanner new_scanner = new Scanner(new_scanner);
int radius = new_scanner.nextInt();
new_scanner.close();
double min_max_dist = Double.MAX_VALUE; // 初始化为最大值，以便后续更新
int[] result_pair = new int[2]; // 存储最终结果 (x, y)
// 优化i的遍历范围：
// 1. i <= radius 是显而易见的。
// 2. i从 radius / 2 开始是一个常见的启发式优化，因为当i过小时，j会非常接近radius，
// 此时sqrt(i^2 + j^2)会略大于radius，但通常不是最小的。
// 最小的距离通常发生在i和j的值相对接近时（例如i和j都接近r/sqrt(2)）。
// 这个范围确保了我们能找到最优解，同时避免了不必要的早期迭代。
for (int i = (radius / 2); i <= radius; i++) {
// 计算j的最小起始值，使其满足 j > sqrt(r^2 - i^2)
// Math.pow(radius, 2) - Math.pow(i, 2) 确保了平方根内的值非负，因为 i <= radius
int start_j_from_inequation = (int) Math.floor(Math.sqrt(Math.pow(radius, 2) - Math.pow(i, 2))) + 1;
// 确保 j >= i，并使用上面计算出的最小j值
int j = Math.max(i, start_j_from_inequation);
// 计算当前 (i, j) 对的距离
double current_dist = Math.sqrt(Math.pow(i, 2) + Math.pow(j, 2));
// 检查当前距离是否大于半径且小于已找到的最小距离
// current_dist > radius 条件在 j 的计算中已经隐含满足，但显式检查更清晰
if (current_dist > radius) {
if (min_max_dist > current_dist) {
min_max_dist = current_dist;
result_pair[0] = i;
result_pair[1] = j;
}
}
}
System.out.println(result_pair[0] + " " + result_pair[1]);
}
}示例
让我们通过几个例子来验证这个算法：
-
半径 r = 1：
- i 从 1/2 = 0 开始，向上取整为 1。
- 当 i = 1 时：
- start_j_from_inequation = floor(sqrt(1^2 - 1^2)) + 1 = floor(sqrt(0)) + 1 = 1。
- j = max(1, 1) = 1。
- 距离 sqrt(1^2 + 1^2) = sqrt(2) ≈ 1.414。
- 1.414 > 1，且这是第一个有效距离，所以 (1, 1) 被记录。
- 最终输出：1 1
-
半径 r = 5：
- i 从 5/2 = 2 开始。
- 当 i = 2 时：
- start_j_from_inequation = floor(sqrt(5^2 - 2^2)) + 1 = floor(sqrt(21)) + 1 = floor(4.58) + 1 = 4 + 1 = 5。
- j = max(2, 5) = 5。
- 距离 sqrt(2^2 + 5^2) = sqrt(4 + 25) = sqrt(29) ≈ 5.385。
- 5.385 > 5，记录 (2, 5)。
- 继续遍历 i = 3, 4, 5，会发现它们产生的距离都大于 sqrt(29)。
- 最终输出：2 5
-
半径 r = 10：
- i 从 10/2 = 5 开始。
- 当 i = 5 时：
- start_j_from_inequation = floor(sqrt(10^2 - 5^2)) + 1 = floor(sqrt(75)) + 1 = floor(8.66) + 1 = 8 + 1 = 9。
- j = max(5, 9) = 9。
- 距离 sqrt(5^2 + 9^2) = sqrt(25 + 81) = sqrt(106) ≈ 10.295。
- 10.295 > 10，记录 (5, 9)。
- 继续遍历 i = 6, 7, 8, 9, 10，会发现它们产生的距离都大于 sqrt(106)。
- 最终输出：5 9
注意事项与总结
- 数据类型： 尽管半径r是整数，但距离计算涉及平方根和浮点数，因此min_max_dist必须是double类型。
- 边界条件： Math.floor(Math.sqrt(...)) + 1确保了j严格大于sqrt(r^2 - i^2)。
- i的遍历范围： i从radius / 2开始是一个经验性的优化，它显著缩小了搜索空间，同时保证了找到全局最优解。如果从1开始，算法仍然是线性的，但常数因子会略大。
- 性能： 这种优化将时间复杂度从O(radius^2)降低到O(radius)，使得算法对于大半径值（如10000甚至更大）也能在毫秒级内完成计算，极大地提升了效率。
通过深入理解问题背后的数学原理，并巧妙地运用不等式和循环优化，我们能够将一个看似复杂的几何搜索问题转化为一个高效的线性时间算法。
