Find Nearest Points The GPS navigation system uses the graph and geometric algor

Question

Find Nearest Points

The GPS navigation system uses the graph and geometric algorithms to calculate distances and map a route. One of the geometric problems is the closest-pair problem. Given a set of points, the closest-pair problem is to find the two points that are nearest to each other. Write a program that computes the distances between all pair of points and find the one with the minimum distance as follows:

1.Ask the user to enter the number of points.
2.Ask the user to enter x and y positions for each point. Store the positions in a 2-D array. What should the dimensions of the 2-D array be?
3.Compute the distance between the first two points and initialize the variable that represents the shortest distance. Recall that the distance between the two points (x1, y1) and (x2, y2) is computed by taking the square root of the quantity (x1 - x2)^2 + (y1 - y2)^2.
4.Use a nested for loop to compute the distance for every two points and update the shortest distance and the two points with the shortest distance.
5. Display the shortest distance and the closest two points.

Explanation / Answer

please rate - thanks

message me if any problems

import java.util.*;
public class FindNearestPoints
{
public static void main(String[] agrs)
{
int short1=0,short2=0,points,i,j,x,y;
Scanner scan = new Scanner(System.in);
System.out.print("How many points do you have? ");
points=scan.nextInt();
int[][] table = new int[2][points];
double distance,shortest=999999999;
for(i=0;i<points;i++)
   {System.out.println("For point "+(i+1));
    System.out.print("Enter x: ");
    table[0][i] = scan.nextInt();
    System.out.print("Enter y: ");
    table[1][i] = scan.nextInt();
    }
for(i=0;i<points-1;i++)
     for(j=i+1;j<points;j++)
         {x = table[0][i] - table[0][j];
          y = table[1][i] - table[1][j];
          distance = Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
          System.out.println("distance between points "+i+" and "+j+": "+distance);
            if(distance<shortest)
                   {shortest=distance;
                    short1=i;
                    short2=j;
                    }
            }
System.out.println("Shortest distance:"+shortest);
System.out.println("points: "+(short1+1)+": ("+table[0][short1]+","+table[1][short1]+
                   ") and "+(short2+1)+": ("+table[0][short2]+","+table[1][short2]+")");
}
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.