Closest Random Points (Also for Core/Database Engineering)

Find the minimum squared Euclidean distance between distinct point entries; coinciding entries have distance 0. The original problem mentions uniform random generation, but correctness must not depend on randomness. The 100,000 points are kept rather than reduced to 2000.

输入格式

The first line contains n, followed by n lines of x y. Original range: 2≤n≤1000 or n=100000; 0≤x,y≤10⁹−1. Computations and comparisons use exact 64-bit integers; floating-point squared values must not be used.

输出格式

Output the single integer required by the problem.

样例 1

输入：

3
0 0
1 1
2 4

输出：

2

样例 2

输入：

2
7 7
7 7

输出：

0

样例 3

输入：

2
0 0
999999999 999999999

输出：

1999999996000000002

样例说明

The answers to the three public examples are, in order: 2; 0; 1999999996000000002. All examples have been verified by independent small-scale enumeration or state search.