No.2315 Flying Camera
タグ : / 解いたユーザー数 195
作問者 : 👑
amentorimaru
/ テスター :
👑 
tatyam
cleantted
問題文
仮想空間で $N$ 匹のエトワーニュくんが $2$ 次元座標に散らばっています。かわいいですね。
この仮想空間における位置は $2$ 次元の直交座標で表され、$i$ 匹目のエトワーニュくんは座標 $(X_i,Y_i)$ にいます。
あなたはドローンカメラを飛ばして、任意の $2$ 次元座標の格子点にフォーカスを合わせて写真を撮影することができます。
「それぞれのエトワーニュくんからフォーカスを合わせた格子点までのマンハッタン距離」の合計を $S$ とします。
すなわち、フォーカスを合わせた座標を $(x, y)$ とすると、$S = \displaystyle\sum_{i=1}^N\left(|X_i - x| + |Y_i - y|\right)$ です。
全てのエトワーニュくんをよく撮影できる場所を選びたいので、 $S$ の最小値を求めてください。
入力
$N$ $X_1 \ Y_1$ $X_2 \ Y_2$ $\vdots$ $X_N \ Y_N$
- 入力は全て整数
- $1 \le N \le 300$
- $1 \le X_i, \ Y_i \le 300$
出力
$S$ の最小値を出力し最後に改行してください。
サンプル
サンプル1
入力
4 2 5 1 4 5 2 4 1
出力
12
$(3,3)$ にフォーカスを合わせることで
$1$ 匹目のエトワーニュくんからの距離は$|3-2|+|3-5|=3$
$2$ 匹目のエトワーニュくんからの距離は$|3-1|+|3-4|=3$
$3$ 匹目のエトワーニュくんからの距離は$|3-5|+|3-2|=3$
$4$ 匹目のエトワーニュくんからの距離は$|3-4|+|3-1|=3$
$S=12$ となりこれが最小である為この値を出力します。
他にも$(4,4)$ でも $S=12$ となります。
サンプル2
入力
3 100 100 100 100 100 100
出力
0
全てのエトワーニュくんは同じ場所にいるため同じ場所にフォーカスを合わせれば $S=0$ でもふもふ撮影を堪能できます。
サンプル3
入力
8 12 18 5 11 30 5 19 19 23 15 6 6 2 28 2 12
出力
115
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。