2310. Name the Closest Pair Not Just Its Distance

Given n points with integer coordinates, print the two points that are closest together.

Several pairs can tie, so the answer has to be pinned or the question is unanswerable. The rule is: among all pairs achieving the smallest squared distance, print the lexicographically smallest, where a pair is first written with its lexicographically smaller point first, and two pairs are then compared as the four numbers x1 y1 x2 y2 in that order.

(0,0) (1,0) (2,0) (3,0) -> 0 0 three pairs tie at distance 1, 1 0 and (0,0) (1,0) is the smallest (0,0) (0,0) (9,9) -> 0 0 a position repeated is a valid pair 0 0 at squared distance 0

## What most people try first

Returning whichever pair the search happened to find. #2309 computes the smallest squared distance in O(n log^2 n) with a divide and conquer, and the temptation is to carry the pair along with the value. That does find SOME minimising pair, but it does not find them all, so it cannot break the tie: the recursion stops examining pairs once they cannot improve delta, and a pair that merely EQUALS delta is exactly such a pair. So the fast method answers a different question than the one asked here.

## The method, and why n is small

best = the smallest squared distance, over all pairs answer = the lexicographically smallest pair achieving best

Two quadratic passes, which is why this problem bounds n at 2000 rather than at 200000. Finding every minimising pair in O(n log n) is possible, but it needs a grid whose cell side is derived from the minimum distance, and that is a different lesson from this one. The honest statement of the tradeoff is part of the problem: when the question changes from "the minimum" to "which pair", the algorithm that computed the minimum may stop being usable.

## Why the tie rule is the one to pick

A tie rule has to be total, computable without any arithmetic beyond comparison, and independent of the input order, or two correct programs will disagree. Ordering the two points within the pair first, then comparing the four numbers, satisfies all three: it never consults the order the points were typed in, and it always names exactly one pair, because two distinct pairs cannot agree on all four numbers.

## The degenerate case, settled

A position given twice is a legitimate pair at squared distance 0, so the answer may print the same coordinates on both lines. This is a real reading decision: the alternative, requiring the two points to be at different positions, gives a different answer on the same input, and the statement commits to counting the copies as two points.

## Width

With |x|, |y| <= 10^6 a squared distance reaches 8 * 10^12, which overflows a signed 32-bit integer, whose limit is 2147483647. The failure here is visible in the OUTPUT rather than in a number: a wrapped square turns into a negative value, so the wrong pair wins and the program prints two different points. The value is below 2^53 = 9007199254740992, so a JavaScript Number is exact.

## Cost

O(n^2) time with n <= 2000, so about two million pair evaluations, and O(n) memory.

Constraints - `2 <= n <= 2000` - `-1000000 <= x, y <= 1000000` - points need not be distinct; two copies of one position are a valid pair at squared distance `0` - if several pairs tie, the answer is the lexicographically smallest, compared as the four numbers `x1 y1 x2 y2` after ordering the pair internally - a squared distance reaches `8 * 10^12`, so a 64-bit integer is needed