题目内容

某城市正在多个地点部署信号塔，每个信号塔的覆盖区域在二维平面上都是一个圆。给定所有信号塔的平面坐标，需要考察任意两个信号塔之间的相互距离。对于任意两个信号塔 $(x_1,y_1)$ 和 $(x_2,y_2)$，它们之间距离的平方定义为 $(x_1-x_2)^2+(y_1-y_2)^2$。请你求出所有信号塔两两之间距离平方中的最小值。

约束条件：

• 信号塔数量 $n$ 满足 $2 \le n \le 100000$。
• 每个坐标的绝对值不超过 $100000$。

输入描述

第一行包含一个整数 $n$，表示信号塔的数量。

接下来 $n$ 行，每行包含两个整数 $x$ 和 $y$，以空格分隔，表示一个信号塔的坐标。

输出描述

输出一个整数，表示所有信号塔两两之间距离平方的最小值。

样例1

输入

2
-1 -2
3 4

输出

52

说明

共有 2 个信号塔，坐标分别为 (-1,-2) 和 (3,4)。

它们之间的距离平方为 $(-1-3)^2+(-2-4)^2=(-4)^2+(-6)^2=16+36=52$，因此最小值为 52。

样例2

输入

3
0 0
1 1
2 2

输出

2

说明

共有 3 个信号塔。

所有两两距离平方分别为：

(0,0) 与 (1,1)：$(0-1)^2+(0-1)^2=2$

(0,0) 与 (2,2)：$(0-2)^2+(0-2)^2=8$

(1,1) 与 (2,2)：$(1-2)^2+(1-2)^2=2$

其中最小的是 2，所以输出 2。

样例3

输入

4
0 0
1 0
0 1
-2 -2

输出

1

说明

共有 4 个信号塔。

最小的距离平方来自 (0,0) 与 (1,0)，为 $(0-1)^2+(0-0)^2=1$；同样，(0,0) 与 (0,1) 的距离平方也是 $(0-0)^2+(0-1)^2=1$。

其余点对的距离平方均不小于 1，例如 (1,0) 与 (0,1) 的距离平方为 $(1-0)^2+(0-1)^2=2$，(0,0) 与 (-2,-2) 的距离平方为 $(0-(-2))^2+(0-(-2))^2=8$。

因此最小值为 1。