Touching sticks

Given the coordinates (as doubles) of the end points of two sticks, determine whether or not the sticks touch. They are considered to touch if the corresponding line segments cross over each other or if an end point of one segment lies on the other. Drawing a quick graph of the sample cases is probably a good idea. I'm not going to try and embed pictures here.

The input for each case is 8 doubles on a line separated by spaces. The numbers represent x1 y1 x2 y2 x3 y3 x4 y4 where the first stick is from (x1,y1) to (x2,y2) and the second is (x3,y3) to (x4,y4). The cases end when end of file is reached. For each case, print "Touch" or "Don't touch" describing the sticks.

No case will have all four points on a single line (but three might be collinear in some cases).

Sample input
-------------

-1.0 -2.0 0.0 0.0 1.0 0.0 0.0 2.0
1.0 1.0 -1.0 -1.0 1.0 -1.0 -1.0 1.0
-1.0 -2.0 1.0 2.0 1.0 0.0 0.0 2.0
0.0 1.0 0.0 3.0 0.5 0.0 4.3 0.0
1.0 -6.5 -7.2 8.0 -7.2 8.0 12.0 20.5
0.0 5.0 4.0 -1.0 5.0 3.0 2.0 2.0
-1.0 -2.0 0.0 0.0 1.0 0.0 0.5 1.0

Sample output
-------------

Don't touch
Touch
Touch
Don't touch
Touch
Touch
Don't touch

One approach is to use a method which tells you if three points form a clockwise or counterclockwise cycle. This can allow you to tell if the end points of one stick lie on opposite sides of the line extending the other stick. If that is true for each stick, then they touch. The code relies on a method for signed area of a triangle which is based on the vector cross product.

double signed_area(Point2D.Double p1, Point2D.Double p2, Point2D.Double p3)
{
	return (p1.x*p2.y + p3.x*p1.y + p2.x*p3.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y)/2.0;
}

This method returns plus or minus the area of the triangle with vertices p1, p2, and p3. The result is positive if the order p1, p2, p3 moves in a counterclockwise direction and negative for clockwise direction. If the three points are collinear, the answer is zero. Allowing for round-off errors, I would suggest testing signed_area > epsilon, signed_area < -epsilon, and Math.abs(signed_area) <= epsilon for some small value epsilon (say 10e-6 or so).

NOTE: Whether positive signed area corresponds to counterclockwise order depends on whether you have the y-coordinate increasing upwards (like standard math graphing) or increasing downwards (like standard screen coordinates). However, clockwise order will always give you the opposite sign from counterclockwise.