Can the same point appear more than once in the input file? You may assume the data has been preprocessed so that this does not happen.
How do I sort a subarray? Arrays.sort(a, lo, hi) sorts the subarray from a[lo] to a[hi-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 for 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 slides. 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.
My program works except on (some) vertical line segments. What could be going wrong? Are you dividing by zero? With integers, this produces a runtime exception. With floating point numbers, 1.0/0.0 is positive infinity, whereas -1.0/0.0 is negative infinity.
I'm having trouble getting a minimal representation of the line segments in Fast.java when there are 5 or more points on a line segment. Any advice? Not handling the 5-or-more case will lead to only a minor deduction, so don't kill yourself over it.
Can I sort by slope instead of angle? Yes, the atan function is monotonic, so sorting by y/x and atan(y/x) leads to the same result.
Does (Math.atan(y/x) == Math.atan((c*y) / (c*x))) if x, y, and c are integer-valued doubles between 0 and 32,767 with c not equal to zero? Yes. In IEEE floating point, integer are represented exactly (assuming no overflow). Thus c*x and c*y are represented exactly. The result of an IEEE floating point operation is the nearest representable value. Thus, y/x and (c*x)/(c*y) will yield exactly the same value. Therefore, the two expression will be exactly equal. It's sometimes ok to compare floating point numbers for exact equality (but be sure that you know what you're doing!)
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.
Why are most of the line segments in the input files horizontal and vertical? We generate most of the data sets at random. Since they have integer coordinates in a small range, there are more opportunities to form horizontal and vertical lines.
Input. The directory collinear contains some sample input files. Thanks to Jesse Levinson '05 for the remarkable input file rs1423.txt.
Reference solutions. Some of the input files have associated .png files that contain the desired output. You can use these for checking your work.
These are purely suggestions for how you might make progress. You do not have to follow these steps.
The files Point.java and PointPlotter.java comprise a program that reads in a list of points and plots the results. To plot the points, type the following at the command line
This opens a graphical window where you will see the points plotted.% javac PointPlotter.java % java PointPlotter < input56.txt
that returns the tangent of the angle that b makes with a. You can use the Java function Math.atan() for this: it returns an angle between -pi/2 and pi/2. 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)
Now, iterate through all 4-tuples and check if the 4 points are collinear.public static boolean areCollinear(Point a, Point b, Point c, Point d)
It's also worth thinking about how to avoid printing out different representations of the same line segment (when there are exactly 4 points on the line) since you will need this insight for Fast.java. One approach is to only print out the line segment if the 4 points are in ascending order (say relative to y-coordinate, breaking ties by x-coordinate).
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.