問題一覧 >
通常問題
No.1998 Manhattan Restaurant
問題文最終更新日: 2024-11-28 20:21:03
問題文
二次元平面上に 1,2,…,N の番号が付いた N 軒の民家があり、民家 i (1≤i≤N)
の座標は (Xi,Yi) です。
ただし、Xi,Yi はどちらも偶数とします。
コアさんは、この平面上の好きな場所を自由に 2 箇所選び、それぞれに飲食店を建設することにしました。
民家 i (1≤i≤N) から 2 箇所の飲食店までのマンハッタン距離のうち小さい方の値を di とするとき、
max(d1,d2,…,dN) の値としてあり得るものの最小値を求めてください。
なお、本問の制約下において、答えは必ず整数となることが保証されます。
「マンハッタン距離」の定義(クリックで展開)
二次元平面上の任意の 2 点 P1(x1,y1), P2(x2,y2) について、
これら 2 点間のマンハッタン距離 L1(P1,P2) は次のように定義されます。
L1(P1,P2):=∣x1−x2∣+∣y1−y2∣
制約
1≤N≤105
N は整数
−109≤Xi,Yi≤109 (1≤i≤N)
Xi, Yi (1≤i≤N) は偶数
小課題
yukicoderの仕様上、本問に部分点は設定されていませんが、
本問のテストケース(入力)は次の 2 つの小課題によって区分されています。
N≤600 (上から 15 番目のテストケースまで)
追加の制約はない
提出された解答については、小課題1・小課題2ともに正解である場合にのみ AC
と判定されます。
小課題1・小課題2のうち少なくとも一方で不正解である場合には AC
と判定されませんので、予めご了承ください。
入力
入力は次の形式で与えられます。
N
X1 Y1
X2 Y2
⋮
XN YN
出力
答えを 1 行に出力し、最後に改行してください。
サンプル
サンプル1
入力
3
2 6
-16 20
0 -2
出力
5
例えば、2 軒の飲食店をそれぞれ座標 (1,2), (−16,20) に建設すれば良いです。
この場合、
d1=min(∣2−1∣+∣6−2∣,∣2−(−16)∣+∣6−20∣)=5,
d2=min(∣−16−1∣+∣20−2∣,∣−16−(−16)∣+∣−20−(−20)∣)=0,
d3=min(∣0−1∣+∣−2−2∣,∣0−(−16)∣+∣−2−20∣)=5
であり、max(d1,d2,d3)=5 です。
max(d1,d2,d3) の値をこれより小さくすることはできないので、答えは 5 となります。
既に民家が存在する座標に飲食店を建設しても構いません。
サンプル2
入力
10
0 12
0 2
4 4
0 12
0 2
0 2
2 0
4 8
0 4
0 8
出力
4
複数の民家が同じ座標に存在する場合もあります。
サンプル3
入力
1
100 100
出力
0
サンプル4
入力
10
826 -42644
328 6
620390134 -10369824
-28 305164020
-222219018 -3308
406 467945990
1051026 165620000
178174 -38
-28875428 -515082
-73139174 -121760098
出力
345084361
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。