Segment Intersection — Failing on Unknown Edge Cases

I was recently at a programming competition. One of the problems was to determine whether two line segments are parallel, intersect, or do not intersect.

For all of the test cases I ran, my solution worked. However, when I submitted it, it was rejected (but no other information was given). I suspect there is either some edge case I am completely missing... or perhaps the judges messed up.

Input is entered as follows:

ax ay bx by cx cy dx dy

where the first segment is given by $$(a_x, a_y), (b_x, b_y)$$ and the second by $$(c_x, c_y), (d_x, d_y)$$

Some other rules/assumptions:

-
We may assume that no segment has length zero; that is, each segment has distinct endpoints.

-
Segments may share endpoint(s) with the other segment. Endpoints are included in the segment and thus are able to intersect (this also means that a segment whose endpoint lies within the other segment will intersect)

-
Lines which both intersect and are parallel (either partial or complete overlap) should be considered parallel.

-
All coordinates are integers on the open interval (-1000, 1000).

Here's a screenshot of the problem. Note that I'm ignoring the multiple tests option because I highly doubt that was the issue.

```
import java.util.Scanner;

public class QP1505
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);

int ax = in.nextInt();
int ay = in.nextInt();
int bx = in.nextInt();
int by = in.nextInt();
int cx = in.nextInt();
int cy = in.nextInt();
int dx = in.nextInt();
int dy = in.nextInt();

in.close();

/*
* Cross multiply to check equal slopes This takes care of
* +/- infinity as well as zero
*/
if ((by - ay) (dx - cx) == (dy - cy) (bx - ax))
{
System.out.println("PARALLEL");
}
else
{
double m1 = (double) (by - ay) / (bx - ax);
double m2

Failure cases

I ran your program and was able to find an endless number of failures. My technique was to have one line touch the origin (0,0) and then generate all lines that pass directly through the origin by simply choosing mirrored coordinates. I was hoping to find roundoff errors and I did. Here are just a small sampling of failure cases, all of which print "Do not intersect" instead of "intersect":

0 0 0 5 7 29 -7 -29
0 0 0 5 11 -30 -11 30
0 0 0 5 11 -15 -11 15
0 0 0 5 11 25 -11 -25
0 0 0 5 13 -30 -13 30
0 0 0 5 13 -15 -13 15
0 0 0 5 13 27 -13 -27
0 0 0 5 14 29 -14 -29
0 0 0 5 19 21 -19 -21
0 0 0 5 21 23 -21 -23
0 0 0 5 21 27 -21 -27
0 0 0 5 22 -30 -22 30
0 0 0 5 22 -15 -22 15
0 0 0 5 22 25 -22 -25
0 0 0 5 23 -26 -23 26
0 0 0 5 23 -13 -23 13
0 0 0 5 23 27 -23 -27
0 0 0 5 25 -29 -25 29
0 0 0 5 25 7 -25 -7
0 0 0 5 25 14 -25 -14
0 0 0 5 25 28 -25 -28
0 0 0 5 26 -30 -26 30
0 0 0 5 26 -15 -26 15
0 0 0 5 26 27 -26 -27
0 0 0 5 27 29 -27 -29
0 0 0 5 28 29 -28 -29
0 0 0 5 29 15 -29 -15


Floating point?

My personal opinion about solving this problem correctly is that if your coordinates are constrained to be within -1000..1000, then you can do the whole problem using integers and not use floating point at all.

What you would need to do is create a fraction class that holds a numerator and denominator. The fraction class needs to be able to: multiply, divide, add, subtract, compare (i.e. everything you are doing with your doubles). Since the range of coordinates is so small, you shouldn't have a problem with overflow. By doing this you will be safe from roundoff errors.

StackExchange Code Review Q#87975, answer score: 7