Finding the smallest distance between origin and coordinates (larger than radius) in Java

Question

Given a radius, find the coordinates (x, y) such that the distance between (x, y) to the origin is greater than the radius. However, I want to find the distance that is the smallest distance that is greater than the radius. Problem is seen here: open.kattis.com/problems/discdistrict. My code works well for radii that are less than or equal to 5000. However, for large radii, my code starts to break and takes exponentially longer to finish!! Are there any ideas?

Examples: 1 yields (1, 1). 5 yields (2, 5). 10 yields (5, 9). (radius | radius >= 10,000) takes an exponentially long period of time.

import java.util.ArrayList;
import java.util.Collections;
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();

        //ArrayList<Double> new_distance = new ArrayList<>();

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

Thanks again!

If you always return a point on the line x = 0, you can do this without any calculations at all. Please clarify the requirements. — tgdavies, Nov 20 '22 at 00:22
So, what's wrong with `(0, radius + min)` or `(radius + min, 0)`, where `min` is the minimum difference? — Old Dog Programmer, Nov 20 '22 at 00:30

Jérôme Richard · Accepted Answer · 2022-11-20T03:27:32.597

It does not takes an exponential time to finish, just a quadratic time, that is O(radius² / 4). This is because you use 2 nested loops. You can speed up the inner-most loop by just solving a basic conic inequation.

Indeed, you are searching for j values where sqrt(i² + j²) > r with r = radius. This means i² + j² > r² since all values are expected to be positives ones. This means j² > r² - i² and so j > sqrt(r² - i²). As a result, you can start the second inner loop to the value Math.sqrt(Math.pow(r, 2) - Math.pow(i, 2)) if it is bigger than i (note that the expression in the square root is always positive since i <= r).

The resulting code is:

        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++) {
                System.out.println(i + " " + j);
            }
        }

Note that if you want to get one value, you can just use a break instruction so to avoid many unneeded computations.

Assuming the initial code is correct and you really need all the values to be printed, the complexity of the new code is optimal (each iteration is done in a constant time and is strictly useful since it results in a printed line), but it is still quadratic. A deeper analysis of the code shows its (optimal) complexity is O(radius² / 11.68). Thus the new code is only about ~3 times faster in theory. It can still be slow since there are a lot of values to be printed. It may be interesting to better control when the output is flushed.

Update:

Based on the additional information (about the distance being minimized and only one solution required to be printed), here is the resulting code:

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

This code find the solution that minimize the distance. It runs in O(n/2) time, that is, a linear time.

Thank you for your help, Jérôme Richard. This was a question with respect to https://open.kattis.com/problems/discdistrict. The solution for 90210 is supposed to return: 69551 57450, but with your snippet of code AND the code I have when I just return after I find one particular coord, I receive: 45105 78125. — ArbIn, Nov 20 '22 at 01:47
This is certainly because the website ask to return not the first solution found like in your initial code but *the closest one*. `sqrt(69551²+57450²) = 90210.00000554262` while `sqrt(45105²+78125²) = 90210.73467165645`. You just need to store the `(i, j)` value for each `i` in an array and then print the one minimizing `sqrt(i² + j²)`. Alternatively, you can compute the minimum on the fly (more bug-prone but faster). — Jérôme Richard, Nov 20 '22 at 02:14
So, I have a solution that works for me (on my ide), but still gives me a problem when I submit my solution to the website. TLE error. Would you mind letting me know what I am doing wrong here? I have implemented your suggestion, Jerome, but I am still getting that TLE error. — ArbIn, Nov 20 '22 at 02:49
You do not need to take the minimum of all `(i, j)` tuple for all possible `j` value. Only the first `j` value is enough since all other `j` should result in a bigger distance compared to the first one. There is no need for the inner loop in the end. I updated the answer to provide a code doing that. — Jérôme Richard, Nov 20 '22 at 03:26
I have updated my code to include your suggestions. It works for 15/23 cases... Not sure if you are able to find the edge case. I will upvote anyway since you helped me! — ArbIn, Nov 20 '22 at 04:47

Finding the smallest distance between origin and coordinates (larger than radius) in Java

1 Answers1