/ 
実行時間制限: 5 sec / メモリ制限: 256 MB
配点 : 1200 点
問題文
すぬけくんは旗が好きです。
すぬけくんは N 本の旗を一直線上に並べることにしました。
i 番目の旗は座標 x_i か座標 y_i のどちらかに設置することができます。
すぬけくんは、2 つの旗同士の距離の最小値 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 を座標 1 に、旗 2 を座標 5 に、旗 3 を座標 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
Score : 1200 points
Problem Statement
Snuke loves flags.
Snuke is placing N flags on a line.
The i-th flag can be placed at either coordinate x_i or coordinate y_i.
Snuke thinks that the flags look nicer when the smallest distance between two of them, d, is larger. Find the maximum possible value of d.
Constraints
- 2 ≤ N ≤ 10^{4}
- 1 ≤ x_i, y_i ≤ 10^{9}
- x_i and y_i are integers.
Input
The input is given from Standard Input in the following format:
N x_1 y_1 : x_N y_N
Output
Print the answer.
Sample Input 1
3 1 3 2 5 1 9
Sample Output 1
4
The optimal solution is to place the first flag at coordinate 1, the second flag at coordinate 5 and the third flag at coordinate 9. The smallest distance between two of the flags is 4 in this case.
Sample Input 2
5 2 2 2 2 2 2 2 2 2 2
Sample Output 2
0
There can be more than one flag at the same position.
Sample Input 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
Sample Output 3
17