← 返回题目列表

AtCoder · utpc2022_b

B. 十字激光束

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

配点 : 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 th 和 由于您拿了第 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