← 返回题目列表

AtCoder · arc069_d

F. 标志

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

分数: 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