分数: 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