009 - ヒバラ海に沈む遺跡

アイヅ考古学会は、ヒバラ海に沈む古代国家イワシロの遺跡調査に乗り出した。 遺跡はヒバラ海のどこか一か所に存在する。そこで、探査レーダを使い、海岸線からのレーダ探査で遺跡の位置のおおよその目星を付け、海岸線から最大何メートル離れた位置まで調査しなければならないかを見積もることにした。

上図のような直線で表された海岸線上に観測点を設置し、探査レーダを置く。探査レーダでは、観測点を中心とする、ある大きさの半円の範囲に遺跡があるということしかわからない。しかし、複数の観測データを組み合わせることで、より狭い範囲に絞り込むことができる。

課題

観測点の位置と探査レーダが示す半径からなるいくつかの観測データが与えられたとき、海岸線から最大でどのくらいの距離まで調査する必要があるかを求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

N
x1 r1
x2 r2
: 
xN rN

１行目に探査レーダによって測定されたデータの数N(1≦N≦100000)が与えられる。続くN行に、観測データiの海岸線上での位置をメートル単位で表す整数x_i(0≦x_i≦1,000,000)と、その位置から半径何メートル以内に遺跡が存在するかを表す整数r_i(1≦r_i≦1,000,000)が与えられる。観測点が同じ観測データが２つ以上与えられることもある。

与えられた観測データが複数の場合、それらすべての半円に含まれる点が必ず存在すると考えてよい。

時間制限

入力に対して、実行時間が５秒を超えてはならない。

出力

海岸線から最大で 何メートルまで調査する必要があるかを実数で出力する。ただし、誤差がプラスマイナス0.001メートルを超えてはならない。この条件を満たせば小数点以下は何桁表示してもよい。

入出力例

入力例1

2
0 2
1 2

出力例1

1.936

入力例2

3
0 3
1 2
2 1

出力例2

1.0

入力例3

2
0 1
3 2

出力例3

0.0