Do the segments cross
Two segments AB and CD are given on the plane. Do they have at least one common point? A common point may be the end of a segment, the segments may lie on one line and overlap, and a segment may degenerate into a point if its ends coincide.
The third test is stretches of real streets of Almaty from OpenStreetMap, with coordinates in decimetres. Streets that meet at an intersection touch at their ends, and that is the trickiest case.
Input
The first line holds the number of queries t (1 ≤ t ≤ 20,000). Each of the following t lines holds eight integers xA yA xB yB xC yC xD yD, at most 10⁹ in absolute value.
Output
For each query, YES if the segments have a common point, and NO if not.
Examples
Example 1
9 0 0 4 4 0 4 4 0 0 0 2 2 3 3 5 5 0 0 2 2 2 2 5 0 0 0 4 0 1 1 3 1 0 0 4 0 2 0 6 0 0 0 4 0 2 0 2 5 0 0 4 0 6 0 6 5 3 3 3 3 1 1 5 5 3 3 3 3 3 4 3 4
YES NO YES NO YES YES NO YES NO
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Start with the general case: when do the ends of one segment lie strictly on different sides of the other’s line? Then write out all the cases where one of the cross products is zero, and draw each one.
2The idea
Compute four cross products: d₁ = cross(A, B, C), d₂ = cross(A, B, D), d₃ = cross(C, D, A), d₄ = cross(C, D, B). If d₁ and d₂ have strictly different signs and so do d₃ and d₄, the segments cross at an interior point. In all other cases, if there are common points, one of them is an end of one of the segments. So it is enough to check whether any of the four ends lies on the other segment.
3Walkthrough
A point P lies on segment XY if cross(X, Y, P) = 0, so it is on line XY, and its coordinates stay within the rectangle spanned by X and Y: min(xX, xY) ≤ xP ≤ max(xX, xY), and the same for y.
Why are these five checks enough? If the intersection is not at an interior point of both segments, then either the segments lie on one line, or one of the four points lies on the line of the other segment. If the segments are on one line and overlap, at least one end of one lies inside the other, and the end check catches this. If a segment has degenerated into a point A = B, all the products with it are zero, the strict check does not fire, and the answer comes from the check “A lies on CD”.
Coordinates up to 10⁹: differences up to 2·10⁹, a product up to 4·10¹⁸, a cross product up to 8·10¹⁸, which fits in int64. But the product d₁·d₂ no longer fits, so in Go the signs are compared instead of multiplying the numbers themselves.
3+Solution
4Complexity
O(1) per query: eight multiplications for four products and a few comparisons.
5Common mistakes
- “≤ 0” instead of checking the ends. The condition d₁·d₂ ≤ 0 and d₃·d₄ ≤ 0 seems natural, but for segments on one line all the products are zero, and it answers “yes” even when there is a gap between them. The second example of the statement is exactly this case.
- Only the strict check. Without checking the ends, touches are lost: streets that meet at an intersection are counted as not crossing.
- Overflow in the product of signs. In Go
d1*d2with coordinates of ±10⁹ goes beyondint64and changes sign. - Floating point. The intersection point of the lines through division means fractions and rounding errors. For a yes-or-no answer the signs are enough, and in integers they are exact.