← 返回题目列表

AtCoder · abc139_f

F. 发动机

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

分数: 600 点

问题陈述

E869120 最初站在原点 (0, 0) 在二维平面中。

他有 N 引擎,可按如下方式使用:

  • 当 E869120 使用 i第一个引擎,他的 X- 和 Y- 坐标更改 分别是 x_i 和 y_i。换句话说,如果 E869120 使用 i坐标中的第一个引擎 (X, Y),他会移动到坐标 (X + x_i, Y + y_i).
  • E869120 可以按任意顺序使用这些引擎,但每个引擎最多只能使用一次。他也可能选择不使用某些引擎。

他想要离原点尽可能远。 让 (X, Y) 是他的最终坐标。找出最大可能值 \sqrt{X^2 + Y^2},距原点的距离。

约束

  • 1 \leq N \leq 100
  • -1 \ 000 \ 000 \leq x_i \leq 1 \ 000 \ 000
  • -1 \ 000 \ 000 \leq y_i \leq 1 \ 000 \ 000
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1
x_2 y_2
 : :
x_N y_N

输出

打印距原点的最大可能最终距离,作为实际值。 当真实答案的相对或绝对误差最大时,您的输出被认为是正确的 10^{-10}.


示例输入 1

3
0 10
5 -5
-5 -5

示例输出 1

10.000000000000000000000000000000000000000000000000

到原点的最终距离可以是 10 如果我们以以下三种方式之一使用引擎:

  • 使用引擎 1 移至 (0, 10).
  • 使用引擎 2 移至 (5, -5),然后使用引擎 3 移至 (0, -10).
  • 使用引擎 3 移至 (-5, -5),然后使用引擎 2 移至 (0, -10).

距离不能大于 10,所以最大可能距离是 10.


示例输入 2

5
1 1
1 0
0 1
-1 0
0 -1

示例输出 2

2.828427124746190097603377448419396157139343750753

最大可能的最终距离是 2 \sqrt{2} = 2.82842...。 实现它的方法之一是:

  • 使用引擎 1 移至 (1, 1),然后使用引擎 2 移至 (2, 1),最后使用 Engine 3 移至 (2, 2).

示例输入 3

5
1 1
2 2
3 3
4 4
5 5

示例输出 3

21.213203435596425732025330863145471178545078130654

如果我们使用订单中的所有引擎 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5,我们最终将在 (15, 15),距离 15 \sqrt{2} = 21.2132... 来自原点。


示例输入 4

3
0 0
0 1
1 0

示例输出 4

1.414213562373095048801688724209698078569671875376

可能存在无用的引擎 (x_i, y_i) = (0, 0).


示例输入 5

1
90447 91000

示例输出 5

128303.000000000000000000000000000000000000000000000000

请注意,只能有一个引擎。


示例输入 6

2
96000 -72000
-72000 54000

示例输出 6

120000.000000000000000000000000000000000000000000000000

也只能有两个引擎。


示例输入 7

10
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20

示例输出 7

148.660687473185055226120082139313966514489855137208