Frequently Asked Questions |

**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.

Testing |

**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.

Possible Progress Steps |

These are purely suggestions for how you might make progress. You do not have to follow these steps.

**Getting started.**Download the directory collinear to your system. It contains a number of sample input files and some helper programs. To download all the files at once:*Safari.*Click the ftp link above to mount the ftp site, then drag-and-drop the desired folder from the ftp mount to the desired location.*Internet Explorer.*Click the ftp link above, then right click the desired folder, select Copy To Folder, and choose the desired location.*Firefox.*Install the extension DownThemAll! and use that to download all links from a given page.

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**-
**Brute force.**Before writing any code, think carefully about the point data type operations that you will need to support. A minimalistic approach might involve creating a function

that returns the tangent of the angle thatpublic static double angle(Point a, Point b)

`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 function

that returnspublic static boolean areCollinear(Point a, Point b, Point c)

`true`if`a`,`b`, and`c`are collinear and`false`otherwise. Also consider a 4-argument version.

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). -
**Sorting solution.**Before writing any code, think carefully about the point data type operations that you will need to support. The complicating issue is that the function needed to compare the angles of two points`q1`and`q2`depends on a third point`p`, which changes from sort to sort. One solution is to include a`public`and`final`(but not`static`) instance variable`BY_POLAR_ORDER`in`Point`of type`Comparator<Point>`. This`Comparator`has a`compare()`method so that`compare(q1, q2)`compares the angle that`q1`and`q2`make with the invoking object`p`.

Enrichment |

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.