← 返回题目列表

AtCoder · joi2010ho_d

D. 世博会

中文机器翻译题面 查看原题

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

博覧会 - 原题 PDF 第 1 页
原题PDF第9页
博覧会 - 原题 PDF 第 2 页
原题PDF第10页
可复制的 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