Exposition

Time Limit : 8 sec, Memory Limit : 65536 KB

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。


博覧会

問題

JOI 市では,とある大規模な博覧会を開催することになった.

今回の博覧会には 2 つのテーマがあり,JOI 市にある N 個の展示施設でそれぞれ, 2 つのテーマのうちどちらか一方に沿った展示を行う予定である.

施設の位置は平面座標 (x, y) で表される.位置 (x, y) にある施設から (x′ , y′) にある 施設まで移動するためには, |x − x′| + |y − y′| だけの時間がかかる (整数 a に対して, |a| で a の絶対値を表す).同一テーマ内での統一感を出すため,および一方のテーマ のみに関心を持つ人に不便を感じさせないために,同一のテーマで展示を行ってい る 2 つの施設の間の移動時間がなるべく短くなるようにテーマを割りふりたい.す べての展示施設に同じテーマを割りふらない限り, どのようにテーマを割りふっても よい.

同一のテーマで展示を行っている 2 つの施設の間の移動時間の最大値を M とす る. N 個の展示施設の位置が与えられたとき, M の最小値を求めるプログラムを作 成せよ.

入力

入力ファイルのファイル名は input.txt である.

入力の 1 行目には, 施設の個数 N(3 ≤ N ≤ 100000 = 105 ) が書かれている.入力の i + 1 行目 (1 ≤ i ≤ N) には,各施設の座標を表す 2 つの整数 xi, yi (|xi| ≤ 100000 = 105, |yi| ≤ 100000 = 105 ) が空白区切りで書かれている.これは,i 個目の施設の座標が(xi , yi) であることを表す. 同一の座標に 2 つ以上の施設が存在することはない.

採点用データのうち,配点の 40% 分については, N ≤ 2000 である.

出力

出力ファイルのファイル名は output.txt である.

出力は 1 行のみからなる.同一のテーマで展示を行っている 2 つの施設間の移動 時間の最大値 M の最小値を出力せよ.

入出力例

入力例 1
5
0 0
1 0
-1 -2
0 1
-1 1
 
出力例 1
3

この場合,たとえば座標 (0, 0), (1, 0), (0, 1) にある施設に一方のテーマを,(−1, −2), (−1, 1) にある施設にもう一方のテーマを割りふると,同一のテーマで展示を行う 2 つの施設間の移動時間はすべて 3 以下になる.移動時間をすべて 2 以下にすること はできないので,3 を出力する.

Notes on Submission

標準入出力を行うプログラムを作成して下さい.


Source: 9th Japanese Olympiad in Informatics , 2010-02-14
http://www.ioi-jp.org/