分数: 1200 点
问题陈述
Snuke 喜欢旗帜。
Snuke 正在放置 N 一行上的标志。
的 i-th 标志可以放置在任一坐标处 x_i 或坐标 y_i.
Snuke 认为当两个旗帜之间的距离最小时,旗帜看起来更好, d更大。找出最大可能值 d.
约束
- 2 ≤ N ≤ 10^{4}
- 1 ≤ x_i, y_i ≤ 10^{9}
- x_i 和 y_i 是整数。
输入
输入由标准输入按以下格式给出:
N x_1 y_1 : x_N y_N
输出
打印答案。
示例输入 1
3 1 3 2 5 1 9
示例输出 1
4
最佳解决方案是将第一个标志放置在坐标处 1,坐标处的第二个标志 5 和坐标处的第三个标志 9。两个标志之间的最小距离是 4 在这种情况下。
示例输入 2
5 2 2 2 2 2 2 2 2 2 2
示例输出 2
0
同一位置可以有多个标志。
示例输入 3
22 93 6440 78 6647 862 11 8306 9689 798 99 801 521 188 206 6079 971 4559 209 50 94 92 6270 5403 560 803 83 1855 99 42 504 75 484 629 11 92 122 3359 37 28 16 648 14 11 269
示例输出 3
17