2313. The Closest Red Blue Pair

Each of n points carries a colour, 0 for red or 1 for blue. Print the smallest squared distance between a red point and a blue one. Both colours are guaranteed to occur, so an answer always exists. Pairs of the same colour are ignored entirely, however close they are.

(0,0,red) (3,4,blue) (1,1,red) -> 13 (1,1) to (3,4) (0,0,red) (0,0,blue) -> 0 different colours, same position (0,0,red) (1,0,red) (2,0,red) (10,0,blue) -> 64 the red pairs at distance 1 do not count

## What most people try first

Running the divide and conquer of #2309 and then filtering, which is wrong twice over: it reports a same-colour pair when that is the closest, and filtering afterwards cannot recover the closest CROSS-colour pair because the recursion already discarded it.

The deeper trap is assuming the strip argument transfers. In #2309 the inner scan is short because delta is the minimum distance within each half, so the points of one half are pairwise at least delta apart and only a constant number of them fit in the 2 * delta by delta box. Here delta is the minimum over CROSS pairs only, so nothing at all is known about how closely same-colour points are packed: a thousand red points can sit inside that box, and the inner scan degenerates to a linear walk, making the merge quadratic. The bound is not merely harder to prove, it is false.

## The method

Split the points by colour and compare every red with every blue:

best = min over red r, blue b of d2(r, b)

That is O(R * B), at most O(n^2 / 4), which is why n is bounded at 2000 here rather than at 200000. Honest O(n log n) methods exist, built on a Delaunay triangulation or on a Voronoi diagram, because the closest cross-colour pair is always an edge of the Delaunay triangulation of the whole set. Both are far outside what this topic covers with integer arithmetic alone, and the right answer in an interview is to say which structure you would reach for and why the simple strip bound does not apply.

## Why the split is safe

Nothing about the colours interacts with the geometry: the set of admissible pairs is exactly red times blue, so enumerating that product considers each admissible pair exactly once and no inadmissible one. Taking the minimum over a finite non-empty set is well defined, and the set is non-empty because both colours occur.

## The degenerate cases, settled

A red and a blue point at the SAME position give 0, and that is a valid answer, because the pair is admissible and its squared distance really is zero. Duplicates within one colour change nothing, since same-colour pairs never count. If one colour appears exactly once the answer is the smallest squared distance from that single point to any point of the other colour, which the same double loop produces.

## Width

With |x|, |y| <= 10^6 a squared distance reaches 8 * 10^12, past the 2147483647 a signed 32-bit integer holds, so a 32 bit build overflows and a wrapped square can be negative, which makes a minimum search return the most wrapped value rather than the closest pair. One declared test at the coordinate limit reports -1524072448 under truncation against the true 8000000000000. The value is below 2^53 = 9007199254740992, so a JavaScript Number is exact.

## Cost

O(R * B) time and O(n) memory.

Constraints - `2 <= n <= 2000` - `-1000000 <= x, y <= 1000000` - `c` is `0` or `1`, and both values occur at least once - a red and a blue point may share a position, in which case the answer is `0` - same-colour pairs are ignored however close they are - a squared distance reaches `8 * 10^12`, so a 64-bit integer is needed