题目内容

在一个二维平面上分布着 $n$ 个太空城，编号为 $1$ 到 $n$。第 $i$ 个太空城的坐标为 $(x_i, y_i)$。在初始时刻 $0$，每个太空城同时向其他所有太空城各发射一艘铺设通讯链路的工程船。对于任意两个不同的太空城 $A$ 和 $B$，当太空城 $A$ 向太空城 $B$ 发射的工程船与太空城 $B$ 向太空城 $A$ 发射的工程船在它们连线中点相遇时，$A$ 与 $B$ 之间立即建立一条直接的通讯链路（即只有互为目标的工程船相遇才会建立链路）。两个太空城连通当且仅当存在一系列已建成的链路将它们连接（连通关系具有传递性）。你的任务是求出最早的时刻（以年为单位），使得所有 $n$ 个太空城连通，并将该年数向上取整后输出。

约束条件：

• 太空城数量 $n$ 满足 $2 \le n \le 1000$。
• 坐标满足 $-10^8 \le x_i, y_i \le 10^8$。
• 所有坐标均为整数。
• 工程船的航行速度均为 $1$ 单位距离每年。

输入描述