The Nearest Two

Difficulty: 2200 6000 ms 128 MB

divide-and-conquer geometry

Print the SQUARED Euclidean distance of the closest pair of points (integer, no floating point).

Input: the first line has N (N ≥ 2); the next N lines have distinct points x y.

Output: the minimum squared pairwise distance.

Constraints:

• 2 ≤ N ≤ 10⁵
• |coordinates| ≤ 10⁶

Sample Tests

3
0 0
3 4
0 1

1

2
0 0
5 5

50

Read the Editorial