CF623C Electric Charges

程序员 Sasha 是莫斯科物理技术学院（MIPT）的学生，他需要完成一次实验作业来通过期末考试。 一个实验单元是一个带有标准坐标轴的平面。MIPT 的物理学家们给坐标轴充入了大量电荷：$X$ 轴为正电，$Y$ 轴为负电。 一位经验丰富的实验室工作人员在平面上标记了 $n$ 个整点坐标 $(x_{i}, y_{i})$，并暂停了时间。Sasha 需要使用“原子镊子”将基本粒子放在这些点上。他有无限数量的电子（带负电的基本粒子）和质子（带正电的基本粒子）。在每个标记的点上，他可以放置一个电子或质子。当所有标记的点都被粒子填满后，实验室工作人员会重新启动时间，粒子开始运动，经过一段时间后它们会稳定到某个平衡状态。实验任务的目标是安排这些粒子，使得最终态的直径（即所有粒子点对之间的最大距离）尽可能小。 由于 Sasha 是程序员，他天真地认为所有粒子会“掉落”到各自的轴线上：电子会落到 $X$ 轴上，质子会落到 $Y$ 轴上。我们也采用与 Sasha 相同的模型进行分析。即如果一个点 $(x, y)$ 上放置一个电子，则它最终会到达点 $(x, 0)$；如果放置一个质子，则会到达点 $(0, y)$。 由于实验室辐射较高，为了保护自己的笔记本电脑，Sasha 没有携带它，此时他无法编写程序计算这一最终状态的最小可能直径。因此，你需要替他完成这个计算。 请输出这个集合的最小可能直径的平方。

第一行输入一个整数 $n$（$1 \leq n \leq 100000$），表示平面上被标记的点的数量。 接下来的 $n$ 行，每行输入两个整数 $x_{i}$ 和 $y_{i}$（$-10^{8} \leq x_{i}, y_{i} \leq 10^{8}$），表示第 $i$ 个点的坐标。保证任意两点不重合。

输出一个整数，表示集合最小可能直径的平方。

在第一个样例中，Sasha 将所有点都放置电子，最终所有粒子都会落在同一个点 $(1, 0)$。 在第二个样例中，Sasha 将点 $(1, 10)$ 放置电子，点 $(10, 1)$ 放置质子，最终会形成点集 $(1, 0)$ 和 $(0, 1)$，该集合的直径为 $\sqrt{2}$，其平方为 $2$。 由 ChatGPT 5 翻译