|
|
How should I read from standard input? Write to standard draw? In this course you will use our home-brewed library StdIn.java to read text from standard input and library StdDraw.java to plot graphics on standard draw. For those of you that didn't take COS 126, read Section 1.5 of Introduction to Programming to learn how to use them.
Do I really need to print out and draw a minimal subset of line segments? You should avoid printing overlapping line segments if there are never more than 4 collinear points, e.g., if p2 and p3 are on the line segment p1—p4, print out either p1—p4 or p4—p1, but don't print out p1—p3 or any other sub-segment. You will receive a small bonus if you avoid overlapping line segments in Fast.java when there are 5 or more collinear points, e.g., p2, p3, and p4 are on the line segment p1—p5, print out either p1—p5 or p5—p1, but don't print out p1—p4 or any other sub-segment.
Can the same point appear more than once in the input file? No. You may assume the data has been pre-processed so that this does not happen.
How do I access the mathematical constant π? It's Math.PI, but don't use it or you'll likely encounter floating point roundoff issues.
What's the difference between Math.atan2() and Math.atan()? The former returns an angle between -pi and pi; the latter returns an angle between -pi/2 and pi/2: it treats the angle between the origin and (x, y) as equal to the angle between the origin and (-x, -y). If you want to sort by polar angle, you should use atan2(). However, you might be happy sorting by something other than polar angle.
Does (Math.atan2(y, x) == Math.atan2(c*y, c*x)) if x, y, and c are integers between 0 and 32,768 with c not equal to zero? Yes, although this fact is probably not obvious without an understanding of IEEE floating point arithmetic.
Do I have to implement my own sorting algorithm? No, use Java's system sort Arrays.sort().
Can I sort just part of an array? Sure. Arrays.sort(a, from, to) sorts the subarray from a[from] to a[to-1] according to the natural order of a[]. Use a Comparator as the fourth argument to sort according to an alternate order.
How much extra space can I use? Limit yourself to a constant amount of extra space or Brute.java and a linear amount of extra space for Fast.java. By extra space, we mean beyond the space needed to store the array of points.
Where can I see examples of Comparable and Comparator? See the lecture notes and Section 3.5 of the booksite. We assume this is new Java material for most of you, so don't hesitate to ask if you are unsure of how to use it.
How do I measure the running time of my program in seconds? Either use StopWatch.java as in lecture. It's probably a good idea to redirect output to a file so that you avoid counting the time needed to display the text on the screen.
If you use Linux or OS X, you can use the following command instead:
and look at the output for user time. Note that you should use the full path name; otherwise your shell might use its own built-in time command. Be careful when using /usr/bin/time with piping - it may only time the first process and not the whole chain./usr/bin/time java Hello < input.txt > output.txt
How do I profile my program? Execute with the command
java -Xprof Hello < input.txt > output.txt
|
|
Input. Here are some sample input files. Thanks to Jesse Levinson '05 for the remarkable input file rs1423.txt. To estimate the running time as a function of N, you may use the program Generator.java. It takes a command line argument N and outputs a random instance of N points.
Reference solutions. Some of the input files have associated .png files that contain the desired output. You can use these for checking your work.
Submission. Your two programs must be named Brute.java and Fast.java. Both programs must use a common point data type named Point.java. Be sure to submit every file that your program needs (except StdIn.java and StdDraw.java). Don't forget to hit the "Run Script" button on the submission system to test that it compiles cleanly.
Readme. Use the following readme file template and answer all questions. This includes analyzing the two algorithms both empirically and analytically.
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
This should open up a graphical window where you will see the points plotted.javac PointPlotter.java java PointPlotter < input56.txt
that returns the angle that that b makes with a. The Java function Math.atan2(double y, double x) is exactly what you need: it returns the polar angle that corresponds to the point (x, y) in Cartesian coordinates. Then, use this helper function to create a functionpublic static double angle(Point a, Point b)
that returns true if a, b, and c are collinear and false otherwise. Also consider a 4-argument version.public static boolean areCollinear(Point a, Point b, Point c)
public static boolean areCollinear(Point a, Point b, Point c, Point d)
|
|
This problem belongs to a group of problems that are known as 3SUM-hard. It is conjectured that such problems have no subquadratic algorithms. Thus, the sorting algorithm presented above is about the best we can hope for (unless the conjecture is wrong). Under a restricted decision tree model of computation, Erickson proved that the conjecture is true.