寻找Java中原点到坐标（大于半径）的最小距离_技术教程

本文旨在优化Java程序，使其能高效地找到距离原点大于给定半径的最小坐标点。原始代码在处理大半径时效率较低，本文通过数学优化和算法改进，将时间复杂度从平方级降低到线性级，显著提升程序性能，并提供优化后的代码示例。

在解决寻找距离原点大于给定半径的最小坐标点的问题时，原始代码由于使用了嵌套循环，导致时间复杂度较高，尤其是在处理大半径时，效率显著下降。本文将介绍如何通过数学推导和算法优化，显著提升程序的性能。

问题分析

问题的核心在于找到满足 sqrt(x² + y²) > radius 条件的坐标 (x, y)，并使得 sqrt(x² + y²)的值尽可能小。原始代码采用遍历的方式，效率较低。

优化方案

优化方案主要集中在减少不必要的计算上。通过数学分析，我们可以避免内层循环的多次迭代。

内层循环优化：
已知 sqrt(x² + y²) > radius，可以推导出 y > sqrt(radius² - x²)。因此，内层循环的起始值可以直接计算得到，避免了对小于该值的 y 进行不必要的判断。
线性时间复杂度：
由于只需要找到一个满足条件的坐标点，并且需要最小化距离，因此可以在找到第一个满足条件的 y 值后，直接跳出内层循环。

优化后的代码

以下是优化后的 Java 代码：

public class disc_district {

    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 - 1;
        int[] new_min_pair = new int[2];

        for (int i = (radius / 2); i <= radius; i++) {
            int start = (int)Math.floor(Math.sqrt(Math.pow(radius, 2) - Math.pow(i, 2))) + 1;
            int j = Math.max(i, start);
            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]);
    }
}

代码解释

start = (int)Math.floor(Math.sqrt(Math.pow(radius, 2) - Math.pow(i, 2))) + 1;: 根据公式计算内层循环的起始值，避免不必要的迭代。 Math.floor用于向下取整，+ 1保证结果大于根号值。
int j = Math.max(i, start);: 确保 j 不小于 i，并从计算出的起始值开始。
if (new_dist > radius): 检查当前坐标是否满足距离大于半径的条件。
if (min_max_dist > new_dist): 找到更小的距离时，更新最小距离和对应的坐标。