B - Cross Laser Beam Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

2 次元平面上に nok0 君と N 匹のスライムがいます。はじめ nok0 君の座標は (0, 0)、i\ (1\le i\le N) 番目のスライムの座標は (X_i, Y_i) です。 nok0 君は平面上の任意の地点で何度でも以下の行動ができます。

  • x 軸正負方向、y 軸正負方向の合計 4 方向に同時にビームを打つ。nok0 君と等しい x 座標または y 座標をもつスライムが消滅する。
nok0 君は平面上を任意の方向に連続的に移動することができます。nok0 君が平面上にいるすべてのスライムを消滅させるのに必要な移動距離の最小値を求めてください。

制約

  • 入力は全て整数
  • 1 \le N \le 2000
  • |X_i|, |Y_i| \le 10^8

入力

入力は以下の形式で標準入力から与えられる。

N  
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

答えを 1 行に出力せよ。真の値との絶対誤差または相対誤差が 10^{−6} 以下であれば正解として扱われる。

入力例 1

3
1 -1
2 6
8 3

出力例 1

3.605551275463989

nok0 君は次のように移動とビームの発射を行うことができます。

  • (0, 0) から (1, 1.5) に移動してビームを打つ。1 番目のスライムが消滅する。
  • (1, 1.5) から (2, 3) に移動してビームを打つ。2 番目と 3 番目のスライムが消滅する。

これが最適な移動の方法で、移動距離の合計は \sqrt{13} = 3.605551275\ldots となります。

入力例 2

1
100000000 -100000000

出力例 2

100000000.000000000000000

入力例 3

18
2092413 29557322
-83061793 -86609930
41750783 34587912
94366440 62086679
42714686 -18841496
10264522 -60895144
94721140 -72749181
-68416594 -56662164
85327102 82520146
-97103434 30343456
54136952 -27352836
-38212546 92787647
-72073444 28721824
32088712 -55984481
-38640098 22126296
84969832 -72730101
-4649799 14505075
92214627 89508662

出力例 3

225535157.051134686276782