ch1maera February 2016

Finding Radius of a Circle that Contains All the Points in an Array

I have the following program to write:

Write a program that performs the following: 1. Declare an array of size 20 of type XYPoint. 2. Fill the array with 20 random points. The x- and y-coordinates should contain values between -1000 and 1000 3. Print the contents of the array to the screen. 4. Calculate the radius of the smallest circle, centered at the origin, that will enclose all of the points. This must be done after ALL of the points have been create. 5. Print the radius.

This is my program so far:

import net.apcs.classes.XYPoint;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class EncloseInCircle {
    public static Scanner console = new Scanner(System.in);

    public static void main(String[] args) {
        XYPoint a[];
        a = new XYPoint[20];
        XYPoint random;

        for (int i = 0; i < a.length; i++) {
            Random rand = new Random();
            int x = (rand.nextInt(1001) + 10000);
            int y = (rand.nextInt(1001) + 10000);
            random = new XYPoint(x, y);

            a[i] = random;
        }

        System.out.println(Arrays.toString(a));

    }
}

I'm not quite sure how to find the radius of a circle that encloses all the random points in my array... Any help would be greatly appreciated.

Answers


Payson February 2016

A hint without giving the actual code, because you need to learn from the exercise and code it yourself.

A circle that encompasses the furthest point from the origin will encompass all the other points which are closer to the origin.

Consider looping through all your points and keeping a note of the highest distance from the origin. You will need to use a simple formula to calculate the distance from the origin for each point. This can be considered a radius of a circle.


user2372844 February 2016

This sounds like a homework question. To solve problems like these, I find it easy to first solve the problem for a trivial case, i.e. 1 point, and start working from there.

So, for example, in the trivial case of 1 point, how would you find a radius of a circle (centered at (0,0)), that would encompass this point? That should be straightforward. Now about the case for 2 points? 3?

The algorithm should reveal itself as you work through higher order cases.


emory February 2016

Since I like recursion.

Assuming I had solved the problem for n-1 and I am attempting to solve it for n points:

I would just calculate if the solution (a circle) for the first n-1 points contains the nth point. It either does or does not and what you should do should be obvious in each case. The solution for the base case n=1 should also be obvious.

I just took http://stackoverflow.com/a/35281932/348975's hint and reversed it.

Post Status

Asked in February 2016
Viewed 3,688 times
Voted 8
Answered 3 times

Search




Leave an answer