Closest Pair of Points - Classic Problems | Repovive

CLS43. Closest Pair of Points

3s256 MB

Given $n$ points in the 2D plane with integer coordinates, find the minimum squared Euclidean distance between any pair of distinct points.

The squared distance between points $(x_1, y_1)$ and $(x_2, y_2)$ is $(x_1 - x_2)^2 + (y_1 - y_2)^2$ .

Constraints

$2 \le n \le 50000$
$|x_i|, |y_i| \le 10^9$
All points have distinct coordinates (no two points are the same)

Input

\begin{array}{l} n \\ x_1 \quad y_1 \\ x_2 \quad y_2 \\ \vdots \\ x_n \quad y_n \end{array}

Output

d^2_{\min}

Samples

Input

Explanation

Case 1

The closest pair is

Case 2

(0, 0)

Case 3

and

Case 4

(1, 1)

Case 5

, with squared distance 1 + 1 = 2.

Output

Input

Explanation

All points lie on one line. The closest pair is at coordinates 3 and 5, giving squared distance 4.

Output

Input

Explanation

Case 1

The center point

Case 2

(5, 5)

Case 3

is closest to each corner, and that squared distance is 25 + 25 = 50.

Output

CLS43. Closest Pair of Points

3s256 MB

Given $n$ points in the 2D plane with integer coordinates, find the minimum squared Euclidean distance between any pair of distinct points.

The squared distance between points $(x_1, y_1)$ and $(x_2, y_2)$ is $(x_1 - x_2)^2 + (y_1 - y_2)^2$ .

Constraints

$2 \le n \le 50000$
$|x_i|, |y_i| \le 10^9$
All points have distinct coordinates (no two points are the same)

Input

\begin{array}{l} n \\ x_1 \quad y_1 \\ x_2 \quad y_2 \\ \vdots \\ x_n \quad y_n \end{array}

Output

d^2_{\min}

Samples

Input

Explanation

Case 1

The closest pair is

Case 2

(0, 0)

Case 3

and

Case 4

(1, 1)

Case 5

, with squared distance 1 + 1 = 2.

Output

Input

Explanation

All points lie on one line. The closest pair is at coordinates 3 and 5, giving squared distance 4.

Output

Input

Explanation

Case 1

The center point

Case 2

(5, 5)

Case 3

is closest to each corner, and that squared distance is 25 + 25 = 50.

Output