题目描述

在一片平静的湖面上，散落着 $n$ 个木桩。第 $i$ 个木桩的位置可以表示为平面直角坐标系中的点 $(x_i,y_i)$，保证所有木桩的坐标互不相同。小明准备从 $1$ 号木桩出发，通过在木桩之间不断跳跃，最终到达 $n$ 号木桩。

在跳跃过程中，他可以从当前所在的木桩跳到湖面上任意一个木桩上。如果某次跳跃的距离过长，他就会因为体力不支而掉入水中。因此，他希望规划一条从 $1$ 号木桩到 $n$ 号木桩的跳跃路线，使得在整个路线中，最长的那一次跳跃的距离尽可能短。

为了避免浮点数带来的精度误差，你只需要输出这个“尽可能短的最长跳跃距离”的平方。

输入格式

第一行一个正整数 $n$，表示木桩的数量。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个木桩的平面坐标。

输出格式

输出一行一个整数，表示在最优跳跃路线下，最长跳跃距离的平方。

样例 #1

输入 #1

4
0 0
1 1
3 1
4 0

输出 #1

4

数据范围

• 对于 $20\%$ 的数据，$n \le 100$；
• 对于 $50\%$ 的数据，$n \le 1000$；
• 对于 $80\%$ 的数据，$n \le 5000$；
• 对于 $100\%$ 的数据，$2 \le n \le 5000$，$-10^5 \le x_i,y_i \le 10^5$。