M - Gathering in the Aerial Town
問題文
札幌市では人口増加に伴う住宅用地の不足を受け、空中に家を建てる技術を採用しています。
札幌市には $N$ 軒の家があり、$i$ 番目の家は座標 $(x_i,y_i,z_i)$ に建てられています。今、札幌市は非常に寒いため、すべての住民は自分の家にいます。
$i$ 番目の家に住んでいる住人は座標 $(x,y,z)$ から座標 $(x',y',z')$ に移動するとき、$c_i (|x-x'|+|y-y'|+|z-z'|)$ だけ時間がかかります。
市長であるあなたは、すべての家の住人を座標 $(p,q,r)$ に集めて集会を行います。
$(p,q,r)$ を自由に決められるとき、すべての家の住人を集めるために必要な時間の最小値を求めてください。
より形式的には、$\min\limits_{(p,q,r)\in\mathbb{R}^3}\max\limits_{1\leq i\leq N}\lbrace c_i(|x_i-p|+|y_i-q|+|z_i-r|)\rbrace$ を求めてください。
制約
- $1 \leq N \leq 10^5$
- $-10^{4} \leq x_i,y_i,z_i \leq 10^{4}$
- $1 \leq c_i \leq 10^3$
- 入力はすべて整数である
部分点
set1$(30$ 点$)$： $z_i=0$all$(70$ 点$)$：追加の制約はない
入力
入力は以下の形式で標準入力から与えられます。
$N$
$x_1$ $y_1$ $z_1$ $c_1$
$x_2$ $y_2$ $z_2$ $c_2$
$\vdots$
$x_N$ $y_N$ $z_N$ $c_N$
出力
答えを出力してください。
ただし、想定解との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われます。
2
0 0 0 1
1 1 0 1
1.0000000000
$1$ 番目の家に住んでいる住民は、座標 $(0, 0, 0)$ から座標 $(0.5, 0.5, 0)$ まで移動するのに $1$ の時間がかかります。
また、$2$ 番目の家に住んでいる住民は、座標 $(1, 1, 0)$ から座標 $(0.5, 0.5, 0)$ まで移動するのに $1$ の時間がかかります。
したがって、$1$ の時間ですべての家の住民を座標 $(0.5, 0.5, 0)$ に集めることができます。また、$1$ 未満の時間ですべての家の住民を集めることはできません。
この入力例は部分点 set1 の制約を満たします。
11
2 0 2 4
-71 68 66 46
-83 -1 -59 17
69 24 -8 71
-62 -18 5 39
4 88 -56 21
-8 -97 -64 6
-51 85 51 40
72 89 -53 22
65 50 -52 19
71 35 -86 87
9839.5037593985
4
2 5 2 1
2 5 2 5
2 5 2 52
2 5 2 521
0.0000000000
同じ座標に複数の家が建てられる場合があります。