← 返回题目列表

Codeforces · 623/C

C. 电费

中文机器翻译题面 查看原题

程序员 Sasha 是 MIPT(莫斯科物理技术学院)的学生,他需要做一个实验室工作才能通过期末考试。

实验室单位是一个标有标准坐标轴的平面。莫斯科物理技术学院的物理学家用大电荷给轴充电:X轴为正,Y轴为负。

经验丰富的实验室工作人员在平面上用整数坐标(xi,yi)标记n个点并停止时间。萨沙应该使用“原子镊子”将基本粒子放置在这些点上。他拥有无限数量的电子(带负电的基本粒子)和质子(带正电的基本粒子)。他可以在每个标记点放置一个电子或一个质子。一旦所有标记点都充满粒子,实验室工作人员将再次打开时间,粒子将开始运动,一段时间后它们将稳定在平衡状态。实验室工作的目标是以这样的方式排列粒子,使得所得状态的直径(该组点对之间的最大距离)尽可能小。

由于Sasha是一名程序员,他天真地认为所有粒子都会简单地“落入”它们在相应轴上的投影:电子将落入X轴,而质子将落入Y轴。由于我们也是程序员,因此我们将考虑与Sasha相同的模型。也就是说,如果粒子是电子,则从点 (x, y) 到达点 (x, 0);如果粒子是质子,则从点 (0, y) 到达点 (0, y)。

由于实验室背景辐射较高,而 Sasha 负责保管他的笔记本电脑,因此他没有随身携带笔记本电脑,现在他无法编写程序来计算结果集的最小可能直径。因此,你必须为他做这件事。

打印该组的最小可能直径的正方形。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) - 平面上标记的点数。

接下来的 n 行中的每一行都包含两个整数 xi 和 yi (- 108 ≤ xi, yi ≤ 108)——第 i 个点的坐标。保证没有两点重合。

输出

打印一个整数——该集合的最小可能直径的平方。

示例

输入 #1

3
1 10
1 20
1 30

输出 #1

0

输入 #2

2
1 10
10 1

输出 #2

2

注意

在第一个样本中,Sasha 将电子放在所有点上,所有粒子最终落在一个点 (1, 0)。

在第二个样本中,Sasha 在点 (1, 10) 处放置了一个电子,在 (10, 1) 处放置了一个质子。结果是两个点 (1, 0) 和 (0, 1) 的集合,其直径为 $$\sqrt{2}$$。