Java Reference
In-Depth Information
**22.11
(
Geometry: Graham's algorithm for finding a convex hull
) Section 22.10.2
introduced Graham's algorithm for finding a convex hull for a set of points.
Assume that the Java's coordinate system is used for the points. Implement the
algorithm using the following method:
/** Return the points that form a convex hull */
public static
ArrayList<MyPoint> getConvexHull(
double
[][] s)
MyPoint
is a static inner class defined as follows:
private static class
MyPoint
implements
Comparable<MyPoint> {
double
x
,
y
;
MyPoint
rightMostLowestPoint
;
MyPoint(
double
x,
double
y) {
this
.
x
= x;
this
.
y
= y;
}
public void
setRightMostLowestPoint(MyPoint p) {
rightMostLowestPoint
= p;
}
@Override
public int
compareTo(MyPoint o) {
// Implement it to compare this point with point o
// angularly along the x-axis with rightMostLowestPoint
// as the center, as shown in Figure 22.10b. By implementing
// the Comparable interface, you can use the Array.sort
// method to sort the points to simplify coding.
}
}
Write a test program that prompts the user to enter the set size and the points
and displays the points that form a convex hull. Here is a sample run:
How many points are in the set? 6
Enter 6 points: 1 2.4 2.5 2 1.5 34.5 5.5 6 6 2.4 5.5 9
The convex hull is
(1.5, 34.5) (5.5, 9.0) (6.0, 2.4) (2.5, 2.0) (1.0, 2.4)
*22.12
(
Last 100 prime numbers
) Programming Exercise 22.8 stores the prime num-
bers in a file named
PrimeNumbers.dat.
Write an efficient program that reads
the last
100
numbers in the file. (
Hint
: Don't read all numbers from the file.
Skip all numbers before the last 100 numbers in the file.)
**22.13
(
Geometry: convex hull animation
) Programming Exercise 22.11 finds a con-
vex hull for a set of points entered from the console. Write a program that ena-
bles the user to add/remove points by clicking the left/right mouse button, and
displays a convex hull, as shown in Figure 22.8c.
*22.14
(
Execution time for prime numbers
) Write a program that obtains the execu-
tion time for finding all the prime numbers less than 8,000,000, 10,000,000,
Search WWH ::
Custom Search