Do Two Walls Meet?

A floor plan has straight walls, each drawn as a line segment between two end points. Write segments_touch(a1, a2, b1, b2) that returns True if the segment from a1 to a2 and the segment from b1 to b2 share at least one point, and False otherwise. Every point is an (x, y) tuple of integers.

Sharing a point covers every way of meeting:

• crossing in an X,
• one segment ending on the other (a T shape), or both ending at the same point,
• lying along the same line and overlapping, even if only at one end point.

A segment can have both ends at the same point; it is then a single point.

Examples

segments_touch((0, 0), (4, 4), (0, 4), (4, 0))   # returns True
segments_touch((0, 0), (2, 2), (3, 3), (5, 5))   # returns False
segments_touch((0, 0), (2, 2), (2, 2), (5, 1))   # returns True
segments_touch((0, 0), (4, 0), (2, 1), (2, 3))   # returns False

The first pair cross in the middle. The second pair lie on the same line but leave a gap between (2, 2) and (3, 3). The third pair meet at their shared end (2, 2).

Constraints

• Coordinates are integers between -109 and 109.

Note

Some tests use huge, almost parallel segments. Working out slopes or crossing points with division can round the wrong way there, so stick to whole-number arithmetic such as cross products.