求解Java中原点到坐标的最小距离（大于半径）-java教程-PHP中文网

求解Java中原点到坐标的最小距离（大于半径）

花韻仙語

发布： 2025-10-14 09:39:12

原创

424人浏览过

求解java中原点到坐标的最小距离（大于半径）

本文旨在解决在Java中寻找距离原点大于给定半径的最小距离坐标的问题。原始代码效率较低，特别是对于较大的半径值。本文通过优化内层循环，利用数学不等式简化计算，将时间复杂度从二次方降低到线性，从而显著提高代码的执行效率。同时，提供了优化后的代码示例，并分析了其时间复杂度，帮助读者更好地理解和应用该算法。

在许多几何计算或优化问题中，我们经常需要找到满足特定条件的最近点。本文将探讨如何高效地在Java中找到距离原点大于给定半径的最小距离坐标(x, y)。原始代码使用嵌套循环进行搜索，导致时间复杂度较高，特别是对于较大的半径值。通过优化内层循环的起始条件，我们可以显著提高算法的效率。

问题描述

给定一个半径 r，我们需要找到坐标 (x, y)，使得原点 (0, 0) 到 (x, y) 的距离大于 r，并且该距离是所有满足条件坐标中最小的。

原始代码分析

原始代码使用两层嵌套循环来遍历可能的 x 和 y 值。对于每个坐标 (x, y)，计算其到原点的距离，并检查是否大于半径 r。如果满足条件，则更新最小距离和对应的坐标。

立即学习“Java免费学习笔记（深入）”；

import java.util.Scanner;

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;
            for (int j = Math.max(i, start); 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²)，这是因为存在两个嵌套循环，每个循环的迭代次数与半径成正比。当半径较大时，算法的执行时间会显著增加。

iMuse.AI

iMuse.AI 创意助理，为设计师提供无限灵感！

139

查看详情

优化方法

为了提高算法的效率，我们可以优化内层循环的起始条件。根据距离公式，我们有 sqrt(x² + y²) > r，即 x² + y² > r²。因此，对于给定的 x 值，我们可以计算出 y 的最小值，使得 y > sqrt(r² - x²)。

基于这个不等式，我们可以直接计算内层循环的起始值，避免不必要的迭代。优化后的代码如下：

import java.util.Scanner;

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]);
    }
}

登录后复制

在这个优化后的代码中，内层循环不再需要遍历所有可能的 y 值，而是直接从满足 y > sqrt(r² - x²) 的最小值开始。由于只需要找到一个满足条件的解，找到后就可以直接结束循环。因此，该算法的时间复杂度降低到 O(n/2)，即线性时间复杂度。

总结

通过优化内层循环的起始条件，我们可以显著提高在Java中寻找距离原点大于给定半径的最小距离坐标的算法效率。原始代码的时间复杂度为 O(radius²)，而优化后的代码的时间复杂度为 O(radius)。对于较大的半径值，优化后的代码能够更快地找到满足条件的坐标，从而提高程序的整体性能。在实际应用中，可以根据具体的需求选择合适的算法。如果只需要找到一个满足条件的解，那么优化后的代码是更好的选择。如果需要找到所有满足条件的解，则需要根据实际情况进行调整。

以上就是求解Java中原点到坐标的最小距离（大于半径）的详细内容，更多请关注php中文网其它相关文章！