Java Reference
In-Depth Information
Each row in the array
answers
stores a student's answer, which is graded by comparing it
with the key in the array
keys
. The result is displayed immediately after a student's answer is
graded.
This section presents a geometric problem for finding the closest pair of points.
Key
Point
Given a set of points, the closest-pair problem is to find the two points that are nearest to each
other. In Figure 7.3, for example, points
(1, 1)
and
(2, 0.5)
are closest to each other.
There are several ways to solve this problem. An intuitive approach is to compute the distances
between all pairs of points and find the one with the minimum distance, as implemented in
Listing 7.3.
closest-pair animation on the
Companion Website
(-1, 3)
(3, 3)
(4, 2)
x
y
(1, 1)
0
1
2
3
4
5
6
7
-1
3
(2, 0.5)
-1 -1
1 1
2 0.5
2 1
3
(4, -0.5)
(-1, -1)
(2, -1)
3
4
2
4
-0.5
F
IGURE
7.3
Points can be represented in a two-dimensional array.
L
ISTING
7.3
FindNearestPoints.java
1
import
java.util.Scanner;
2
3
public class
FindNearestPoints {
4
public static void
main(String[] args) {
5 Scanner input =
new
Scanner(System.in);
6 System.out.print(
"Enter the number of points: "
);
7
int
numberOfPoints = input.nextInt();
number of points
8
9
// Create an array to store points
2-D array
10
11 System.out.print(
"Enter "
+ numberOfPoints +
" points: "
);
12
for
(
int
i =
0
; i < points.length; i++) {
13 points[i][
0
] = input.nextDouble();
14 points[i][
1
] = input.nextDouble();
15 }
16
17
double
[][] points =
new double
[numberOfPoints][
2
];
read points
// p1 and p2 are the indices in the points' array
18
int
p1 =
0
, p2 =
1
;
// Initial two points
track two points
track
shortestDistance
19
20
double
shortestDistance = distance(points[p1][
0
], points[p1][
1
],
points[p2][
0
], points[p2][
1
]);
// Initialize shortestDistance
21
22
// Compute distance for every two points
23
for
(
int
i =
0
; i < points.length; i++) {
for each point
i
