#ABC139F. Engines

Engines

题目描述

E869120 is initially standing at the origin (0,0)(0, 0) in a two-dimensional plane.

He has NN engines, which can be used as follows:

  • When E869120 uses the ii-th engine, his XX- and YY-coordinate change by xix_i and yiy_i, respectively. In other words, if E869120 uses the ii-th engine from coordinates (X,Y)(X, Y), he will move to the coordinates (X+xi,Y+yi)(X + x_i, Y + y_i).
  • E869120 can use these engines in any order, but each engine can be used at most once. He may also choose not to use some of the engines.

He wants to go as far as possible from the origin. Let (X,Y)(X, Y) be his final coordinates. Find the maximum possible value of X2+Y2\sqrt{X^2 + Y^2}, the distance from the origin.

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

他有 NN 个发动机,可以如下使用:

  • 当 E869120 使用 ii -th 引擎时,他的 XX - 和 YY - 坐标分别变化了 xix_iyiy_i 。换句话说,如果E869120从坐标 (X,Y)(X, Y) 开始使用 ii /-th引擎,他将移动到坐标 (X+xi,Y+yi)(X + x_i, Y + y_i)
  • E869120 可以按照任意顺序使用这些引擎,但每个引擎最多只能使用一次。他也可以选择不使用其中一些引擎。

他希望从原点出发越远越好。设 (X,Y)(X, Y) 为他的最终坐标。求离原点的距离 X2+Y2\sqrt{X^2 + Y^2} 的最大可能值。

输入格式

输入内容按以下格式标准输入:

NN
x1x_1 y1y_1
x2x_2 y2y_2
:: ::
xNx_N yNy_N

输出格式

以实数形式打印与原点的最大可能最终距离。如果与真实答案的相对误差或绝对误差不超过 101010^{-10} ,则认为输出正确。

样例 #1

样例输入 #1

3
0 10
5 -5
-5 -5

样例输出 #1

10.000000000000000000000000000000000000000000000000

样例 #2

样例输入 #2

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

样例输出 #2

2.828427124746190097603377448419396157139343750753

样例 #3

样例输入 #3

5
1 1
2 2
3 3
4 4
5 5

样例输出 #3

21.213203435596425732025330863145471178545078130654

样例 #4

样例输入 #4

3
0 0
0 1
1 0

样例输出 #4

1.414213562373095048801688724209698078569671875376

样例 #5

样例输入 #5

1
90447 91000

样例输出 #5

128303.000000000000000000000000000000000000000000000000

样例 #6

样例输入 #6

2
96000 -72000
-72000 54000

样例输出 #6

120000.000000000000000000000000000000000000000000000000

样例 #7

样例输入 #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

说明

数据规模与约定

  • 1N1001 \leq N \leq 100
  • 1 000 000xi1 000 000-1 \ 000 \ 000 \leq x_i \leq 1 \ 000 \ 000
  • 1 000 000yi1 000 000-1 \ 000 \ 000 \leq y_i \leq 1 \ 000 \ 000
  • 输入值均为整数。

样例 11 解释

如果我们以以下三种方式之一使用引擎,那么最终的原点距离可以是 1010

  • 使用引擎 11 移动到 (0,10)(0, 10)
  • 使用引擎 22 移动到 (5,5)(5, -5) ,然后使用引擎 33 移动到 (0,10)(0, -10)
  • 使用引擎 33 移动到 (5,5)(-5, -5) ,然后使用引擎 22 移动到 (0,10)(0, -10)

距离不能大于 1010 ,因此可能的最大距离是 1010

样例 22 解释

最大可能的最终距离是 22=2.82842...2 \sqrt{2} = 2.82842... 。其中一种方法是

  • 使用引擎 11 移动到 (1,1)(1, 1) ,然后使用引擎 22 移动到 (2,1)(2, 1) ,最后使用引擎 33 移动到 (2,2)(2, 2)

样例 33 解释

如果我们按照 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$ 的顺序使用所有引擎,我们将在 (15,15)(15, 15) 处结束,与原点的距离为 152=21.2132...15 \sqrt{2} = 21.2132...

样例 44 解释

可能有 (xi,yi)=(0,0)(x_i, y_i) = (0, 0) 没用的引擎。

样例 55 解释

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

样例 66 解释

也只能有两个引擎。