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