← 返回题目列表

Codeforces · 1419/F

F. 火雨

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

表面上有 $$$n$$$ 个脱离体,编号从 $$$1$$$ 到 $$$n$$$,第 $$$i$$$ 个脱离体放置在坐标为 $$$(x_i, y_i)$$$ 的点中。 All detachments are placed in different points.

硫磺应该至少访问每个分队一次。你可以选择硫磺开始的小队。

要从一个小队移动到另一个小队,他应该首先选择四个移动方向(上、右、左、下)之一,然后开始以每秒一个单位间隔的恒定速度移动,直到到达一个小队。当他到达任意支队后,他可以重复相同的过程。

每 $$$t$$$ 秒一次轨道撞击会覆盖整个表面,因此在那一刻硫磺应该位于某个分离点所在的位置。只要需要,他可以留在任何分队。

硫磺是一位优秀的指挥官,这就是为什么他最多可以创建一支小队,并将其放置在任何他想要的具有整数坐标的空点,然后再出发。请记住,硫磺也需要访问该分队。

帮助硫磺并找到最小的$$$t$$$,以便可以检查每个分队。 If there is no such $$$t$$$ report about it.

输入

第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 1000)$$$ — 分队数量。

在接下来的 $$$n$$$ 行中,有一对整数 $$$x_i$$$, $$$y_i$$$ $$$(|x_i|, |y_i| \le 10^9)$$$ — 第 $$$i$$$ 支队的坐标。

保证所有点都不同。

输出

输出最小整数$$$t$$$,以便可以检查最多添加一个新分队的所有分队。

如果没有这样的$$$t$$$,则打印$$$-1$$$。

示例

输入 #1

4
100 0
0 100
-100 0
0 -100

输出 #1

100

输入 #2

7
0 2
1 0
-3 0
0 -2
-1 -1
-1 -3
-2 -3

输出 #2

-1

输入 #3

5
0 0
0 -1
3 0
-2 0
-2 1

输出 #3

2

输入#4

5
0 0
2 0
0 -1
-2 0
-2 1

输出#4

2

注意

在第一个测试中,可以在 $$$(0, 0)$$$ 中放置一个分队,这样就可以检查 $$$t = 100$$$ 的所有分队。可以证明不可能检查所有$$$t < 100$$$的分队;因此答案是$$$100$$$。

在第二个测试中,不存在这样的 $$$t$$$ 可以检查所有分队,即使最多添加一个新分队,所以答案是 $$$-1$$$。

在第三个测试中,可以在 $$$(1, 0)$$$ 中放置一个分队,这样 Brimstone 就可以检查 $$$t = 2$$$ 的所有分队。可以证明它是最小的$$$t$$$。

在第四次测试中,不需要添加任何分队,因为答案不会变得更好($$$t = 2$$$)。可以证明它是最小的$$$t$$$。