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 = (double) (dy - cy) / (dx - cx);
// Find point of intersection
double x, y;
if (Double.isInfinite(m1))
{
x = ax;
y = m2 * (x - cx) + cy;
}
else if (Double.isInfinite(m2))
{
x = cx;
y = m1 * (x - ax) + ay;
}
else
{
x = (m1 * ax - ay - m2 * cx + cy) / (m1 - m2);
y = m1 * (x - ax) + ay;
}
// Check bounds
if (((x >= ax && x <= bx) || (x <= ax && x >= bx))
&& ((y >= ay && y <= by) || (y <= ay && y >= by))
&& ((x >= cx && x <= dx) || (x <= cx && x >= dx))
&& ((y >= cy && y <= dy) || (y <= cy && y >= dy)))
{
System.out.println("INTERSECT");
}
else
{
System.out.println("DO NOT INTERSECT");
}
}
}
}
And some test cases:
Vertical Horizontal, Intersect
0 0 0 5 -1 2 1 2 INTERSECT
Vertical Horizontal, No Intersect
0 0 0 5 1 2 4 2 DO NOT INTERSECT
Horizontal Horizontal, Parallel
0 0 5 0 1 1 5 1 PARALLEL
Vertical Regular, Intersect
0 0 0 5 1 0 -1 4 INTERSECT
Vertical Regular, No Intersect
0 0 0 5 1 0 4 6 DO NOT INTERSECT
Horizontal Regular, Intersect
4 4 7 4 4 3 6 5 INTERSECT
Horizontal Regular, No Intersect
2 2 8 2 3 3 9 6 do not intersect
Regular Regular, Intersect
2 1 4 3 1 2 5 1 INTERSECT
Regular Regular, Parallel
1 2 5 6 3 2 5 4 PARALLEL
Regular Regular, No Intersect
1 2 5 6 3 2 8 5 DO NOT INTERSECT
Let me know if anything else needs to be clarified (or any other test cases).