4460. T3

【题目背景】

小 F 穿越到了一个平行世界，这里的人们所用的装备和我们不一样，小 F 发现这个世界的军事装备是一种名叫魂导器的东西，具体是什么他也说不清楚，需要充能释放，但是由于魂导器产生的能量波动会影响旁边的魂导器。 小 F 所在的地方正处于战场，他被一方军队的人抓住了，小 F 为了使得自己活下来，说明了自己是一个有用的人，他可以帮助军队解决实际问题。 于是元帅告诉了他一个问题，现在全军列装了 $n$ 个联动魂导防御护罩，但是由于魂导器产生的能量波动会影响旁边的魂导器，现在小 F 需要找出使得魂导器两两之间最大的最短距离。 他如果不解决掉就会被杀掉，请你帮助小 F 解决这个问题。

【题目描述】

给定 $n$ 个魂导器的候选坐标 $a_i, b_i$，换言之，第 $i$ 个魂导器只能布置在 $a_i$ 或 $b_i$ 的其中一个位置上，即 $p_i \in \{ a_i, b_i \}$。 定义抗干扰度为： $$ \min_{1 \le i < j \le n} |p_i - p_j| $$ 请你合理安排每个魂导器的部署位置，使得两两之间的最小距离最大化。

【输入格式】

从文件 station.in 中读入数据。 第一行包含一个整数 $n$，表示魂导器的数量。 接下来 $n$ 行，每行两个非负整数 $a_i, b_i$ 表示第 $i$ 个魂导器的候选位置。

【输出格式】

输出到文件 station.out 中。 输出一个整数，表示最小距离最大的答案。

【样例输入】

3
1 8
3 12
6 10

【样例输出】

5

【样例说明】

一种最优的部署方案为：

• 第 $1$ 个魂导器选择坐标 $a_1 = 1$；
• 第 $2$ 个魂导器选择坐标 $b_2 = 12$；
• 第 $3$ 个魂导器选择坐标 $a_3 = 6$。

• $|1 - 6| = 5$；
• $|6 - 12| = 6$；
• $|1 - 12| = 11$。

【数据规模与约定】

对于所有测试数据，保证：

• $2 \le n \le 5 \times 10^4$；
• $0 \le a_i, b_i \le 10^9$；
• 对于任意 $1 \le i \le n$，保证 $a_i \ne b_i$。