2311. How Many Pairs Are Tied for Closest

Given n points with integer coordinates, print how many unordered pairs achieve the smallest squared distance.

(0,0) (1,0) (2,0) (3,0) -> 3 three adjacent pairs at distance 1 (0,0) (1,0) (0,1) (1,1) -> 4 the four sides of the unit square; the diagonals are at squared distance 2 (7,7) (7,7) (7,7) -> 3 three pairs of copies at distance 0 (0,0) (0,0) (1,1) (1,1) -> 2 two pairs at distance 0, one per position

#679 asks the same question in one dimension and prints the PAIRS rather than a count, and the difference is not only the dimension: in one dimension the closest pairs are adjacent after sorting, so there are at most n - 1 of them and they are easy to list, while here the tie count has to be found by search.

## What most people try first

Two separate ideas, both of which go wrong in the same way. The first is to reuse the divide and conquer of #2309, which finds the minimum value but never enumerates every pair attaining it, because it prunes away any pair that merely EQUALS the current best. The second is to count while searching, resetting the counter whenever a smaller distance appears. That is fine, but it has to be a single pass over ALL pairs to be correct, which is the quadratic again.

## The method

best = min over all pairs of d2 answer = number of pairs with d2 equal to best

Two quadratic passes, or one pass that resets the count on a strict improvement and increments it on an exact tie. Both are O(n^2), which is why n is bounded at 2000 here: counting minimum-distance pairs in O(n log n) needs a grid built from the minimum distance, and that is a different lesson.

## Why the count is small but the work is not

In the plane a point can have at most six others at exactly the minimum distance, by a packing argument, so the ANSWER is at most 3n. That is reassuring about the output but says nothing about the search: knowing the answer is small does not tell you where the pairs are, and finding them still requires either all pairs or a spatial index.

## The degenerate case, settled

A position repeated k times contributes k * (k - 1) / 2 pairs at squared distance 0, and if any position repeats then 0 IS the minimum, so the answer is the sum of those counts over all repeated positions and nothing else counts. The fourth worked example above is exactly this case with two positions each doubled, giving 1 + 1 = 2. A statement that left this open would be unanswerable, because deduplicating first gives a completely different number.

## Width

With |x|, |y| <= 10^6 a squared distance reaches 8 * 10^12, past the 2147483647 of a signed 32-bit integer, so a 32 bit build overflows and the wrapped squares compare wrongly, which changes which pairs look tied and so changes the count. The value is below 2^53 = 9007199254740992, so a JavaScript Number is exact. The COUNT itself is at most 3n, well under two million, so it needs nothing wide.

## Cost

O(n^2) time at n <= 2000, and O(n) memory.

Constraints - `2 <= n <= 2000` - `-1000000 <= x, y <= 1000000` - points need not be distinct; a position repeated `k` times contributes `k * (k - 1) / 2` pairs at squared distance `0` - pairs are unordered, so a pair is counted once - a squared distance reaches `8 * 10^12`, so a 64-bit integer is needed