以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
4 博覧会
問題
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 の最小値を出力せよ.
問題4-1
入出力の例
input.txt
5
0 0
1 0
-1 -2
0 1
-1 1
output.txt
3
この場合,たとえば座標(0, 0), (1, 0), (0, 1) にある施設に一方のテーマを,(−1, −2),
(−1, 1) にある施設にもう一方のテーマを割りふると,同一のテーマで展示を行う2
つの施設間の移動時間はすべて3 以下になる.移動時間をすべて2 以下にすること
はできないので,3 を出力する.
問題4-2