2282. How Many Pairs of Segments Meet

n closed segments are given. Print how many of the n * (n - 1) / 2 unordered pairs share at least one point.

3 segments: (0,0)-(4,0), (2,-2)-(2,2), (0,2)-(4,2) -> 2 The first meets the second at (2,0) and the second meets the third at (2,2)`. The first and third are parallel and never meet, so the answer is two and not three.

## What most people try first

A bounding-box test, because it is cheap: two segments can only meet if their boxes overlap. That is a filter and not an answer. Two long diagonals of the same square have identical boxes and meet, while a diagonal and a short segment tucked into a corner have overlapping boxes and do not. Counting box overlaps overcounts, every time.

The second instinct is to count the intersection POINTS. That is a different question and it is not well posed here: two collinear segments that overlap share infinitely many points, so there is no number to add. The question asks for pairs, which is always finite.

## What to do

Test every pair with the exact predicate: the four-sign straddle test for a proper crossing, plus the four on-segment tests that catch every touch, every collinear overlap, and every zero-length segment. Add one for each pair that passes.

With n up to 600 that is at most 179700 pairs, each a handful of integer multiplications, so the quadratic loop is the intended solution rather than a fallback. The bound is deliberately small for that reason: a sub-quadratic count of intersecting pairs needs a sweep line with a balanced structure over the active segments, which is a much longer problem and is not what is being asked here.

## Two counting mistakes to avoid

Count each unordered pair once, so let the inner loop start at i + 1; looping over all ordered pairs doubles the answer. And do not skip i == j by testing coordinates for equality, because two DIFFERENT segments in the input may have identical coordinates, and that pair does meet and must be counted.

## Width

Coordinates satisfy |x|, |y| <= 1000000, so each coordinate difference is at most 2 * 10^6, each product of two differences at most 4 * 10^12, and a cross product at most 8 * 10^12 in magnitude. A signed 32-bit integer stops at 2147483647, so a 32-bit cross product wraps and reports the wrong SIGN, which is a wrong answer and not merely a wrong number. The value is below 2^53 = 9007199254740992, so a JavaScript Number holds it exactly and no BigInt is needed; the bitwise operators must not appear, because they coerce to 32 bits.

The answer itself is at most 179700, which fits anywhere.

Constraints - `1 <= n <= 600` - `-1000000 <= x1, y1, x2, y2 <= 1000000` - a segment may have zero length, and two different segments may have identical endpoints