Engines

题目描述

E869120 最初站在二维平面上的原点 $(0, 0)$。 他有 $N$ 个引擎，可按如下方式使用：

当 E869120 使用第 $i$ 个引擎时，他的 $X$ 和 $Y$ 坐标分别变化 $x_i$ 和 $y_i$。换言之，如果 E869120 在坐标 $(X, Y)$ 使用第 $i$ 个引擎，他将移动到坐标 $(X + x_i, Y + y_i)$。 E869120 可以以任意顺序使用这些引擎，但每个引擎最多使用一次。他也可以选择不使用某些引擎。

他想尽可能远离原点。 设 $(X, Y)$ 为他的最终坐标。求 $\sqrt{X^2 + Y^2}$ 的最大可能值，即到原点的距离。

输入格式

输入按下述格式由标准输入提供： $N$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $:$ $x_N$ $y_N$

输出格式

输出到原点的最大可能最终距离，作为实数。 当你的输出与正确答案的相对误差或绝对误差至多为 $10^{-10}$ 时，将被认为是正确的。

3
0 10
5 -5
-5 -5

10.000000000000000000000000000000000000000000000000

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

2.828427124746190097603377448419396157139343750753

5
1 1
2 2
3 3
4 4
5 5

21.213203435596425732025330863145471178545078130654

3
0 0
0 1
1 0

1.414213562373095048801688724209698078569671875376

1
90447 91000

128303.000000000000000000000000000000000000000000000000

2
96000 -72000
-72000 54000

120000.000000000000000000000000000000000000000000000000

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

148.660687473185055226120082139313966514489855137208

提示

$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$ 输入中的所有数值均为整数。如果按照下面三种方式之一使用引擎，最终到原点的距离可以是 $10$：

使用引擎 $1$ 移动到 $(0, 10)$。 使用引擎 $2$ 移动到 $(5, -5)$，然后使用引擎 $3$ 移动到 $(0, -10)$。 使用引擎 $3$ 移动到 $(-5, -5)$，然后使用引擎 $2$ 移动到 $(0, -10)$。

距离不可能大于 $10$，所以最大可能距离是 $10$。
最大可能的最终距离是 $2 \sqrt{2} = 2.82842...$。 实现该距离的一种方法是：

使用引擎 $1$ 移动到 $(1, 1)$，然后使用引擎 $2$ 移动到 $(2, 1)$，最后使用引擎 $3$ 移动到 $(2, 2)$。
如果我们按顺序 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$ 使用所有引擎，最终会到达 $(15, 15)$，与原点的距离为 $15 \sqrt{2} = 21.2132...$。
可能存在无用的引擎，其 $(x_i, y_i) = (0, 0)$。
注意可能只有一个引擎。
也可能只有两个引擎。

标签: AtCoder|abc139F

来源

AtCoder|abc139F