表面上有 $$$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$$$。