CS
Problems Base course RU

Problem

Where the segments meet

intersections points numerical precision number theory classic interviews

A mapping service merges map layers: roads, rivers, plot boundaries. For each pair of segments it must know whether they meet and where, exactly, without rounding, otherwise the node at the crossing ends up in different places in different layers. Segments may cross, touch with an end, lie on one line with an overlap, and even degenerate into a point.

Input

The first line holds the number of pairs q (1 ≤ q ≤ 10,000). Each following line holds eight integers x1 y1 x2 y2 x3 y3 x4 y4: the first segment from (x1, y1) to (x2, y2), the second from (x3, y3) to (x4, y4). All coordinates are at most 10⁹ in absolute value. A segment’s ends may coincide, and then it is a point.

Output

One line for each pair:

  • NONE if there are no common points;
  • POINT x y if there is one common point: each coordinate is an irreducible fraction p/q with q > 1 or an integer, with the minus before the numerator;
  • SEGMENT x1 y1 x2 y2 if there are infinitely many common points: the ends of the common segment, first the one with the smaller x, and for equal x the smaller y.

Examples

Example 1

Input
8
0 0 4 3 0 3 5 0
0 0 6 0 2 0 2 5
0 0 2 2 2 2 5 0
0 0 4 2 2 1 8 4
0 0 2 1 4 2 8 4
0 0 4 2 0 1 4 3
0 0 10 1 10 2 11 0
-999999937 3 999999929 999999893 5 -999999883 -17 999999991
Output
POINT 20/9 5/3
POINT 2 0
POINT 2 2
SEGMENT 2 1 4 2
NONE
NONE
NONE
POINT -2874999426875025257/249999968875000904 124999970500002335124935227/249999968875000904

Limits

Time · Python
6000 ms
Time · Go
1500 ms
Memory
256 MB
Judging
7 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

Write the segments as A + t·(B − A) and C + u·(D − C), 0 ≤ t, u ≤ 1, and equate them. How do you find t without solving the system head-on? A hint: the cross product of a vector with itself is zero.

2Hint 2

If the cross product of the segments’ directions is zero, the formulas for t and u do not work. Do not rush to answer NONE: what if all four points are on one line?

3The idea

Let r = B − A, s = D − C, den = r × s. If den ≠ 0, then t = (C − A) × s / den and u = (C − A) × r / den; the segments meet if both numbers are in [0, 1], a check in integers without division. The point A + t·r is a fraction. If den = 0 and the points are not on one line, the answer is NONE; if they are, compare the segments along the line, like segments on a number line.

4Walkthrough

Non-parallel. The numerators are tn = (C − A) × s and un = (C − A) × r; if den < 0, flip the signs of all three. They meet if 0 ≤ tn ≤ den and 0 ≤ un ≤ den. The point’s coordinates: x = (Ax·den + tn·rx) / den, and likewise y; reduce the fraction by the greatest common divisor, which Fraction in Python and big.Rat in Go do by themselves.

Parallel. If C or D is not on line AB (or, when A = B, point A is not on line CD), there are no common points. Otherwise all the points are on one line, and along it they are ordered just as the pairs (x, y) are in lexicographic order: by x, and on a vertical line by y. Order each segment’s ends, take lo = the max of the left ends and hi = the min of the right ends. lo > hi is a gap, lo = hi one point, otherwise a common segment from lo to hi. This analysis handles point segments without special cases.

The size of the numbers. Coordinate differences reach 2·10⁹, cross products 8·10¹⁸, on the edge of int64. The numerator of a point’s coordinate reaches 10²⁸, which is already 94 bits. In Python there is no need to think about this; in Go math/big is needed: the eighth example in the statement is a pair of segments whose y numerator is a 27-digit number.

4+Solution
5Complexity

O(1) arithmetic operations per pair, but with long numbers: each on numbers of two or three machine words.

6Common mistakes
  • Parallel means they do not meet. The most common mistake: answering NONE for a zero denominator. Segments on one line can overlap or touch end to end. This is a wrong solution, and the example already catches it.
  • The point in floating point. Even if you then pick a fraction close to the double, with coordinates around 10⁹ it will be the wrong one: a double holds about 16 significant digits, while the answer can have over twenty.
  • Overflow. A coordinate’s numerator does not fit in int64, and a Go solution without math/big prints garbage precisely on the big tests, while on small ones everything is right.
  • Unreduced fractions and -0. The answer is compared as a string: the fraction must be irreducible, the denominator positive, and zero simply 0.

Algorithms behind it

GEO Algorithm Segment intersection Where two segments meet, exactly, in fractions; and how to find all meetings among thousands of segments without trying every pair. O(1) per pair; O(n²) by brute force for n segments 2 problems GEO Technique Vectors and orientation The sign of the cross product is a left or right turn; almost all of computational geometry stands on it. O(1) per turn 2 problems
The algorithms catalogue