AT_arc069_d [ARC069F] Flags

[problemUrl]: https://atcoder.jp/contests/arc069/tasks/arc069_d すぬけくんは旗が好きです。 すぬけくんは $ N $ 本の旗を一直線上に並べることにしました。 $ i $ 番目の旗は座標 $ x_i $ か座標 $ y_i $ のどちらかに設置することができます。 すぬけくんは、$ 2 $ つの旗同士の距離の最小値 $ d $ が大きいほど、旗の並びの見栄えが良いと考えています。$ d $ としてありうる値の最大値を求めなさい。

N/A

N/A

### 制約 - $ 2\ ≦\ N\ ≦\ 10^{4} $ - $ 1\ ≦\ x_i,\ y_i\ ≦\ 10^{9} $ - $ x_i,\ y_i $ は整数 ### Sample Explanation 1 旗 $ 1 $ を座標 $ 1 $ に、旗 $ 2 $ を座標 $ 5 $ に、旗 $ 3 $ を座標 $ 9 $ に設置するのが最適であり、このとき旗同士の距離の最小値は $ 4 $ となります。 ### Sample Explanation 2 旗の位置は重なることもあります。