AT_abc139_f.[ABC139F] Engines

提高+/省选-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

E869120 君一开始站在二维平面上的原点 (0,0)(0, 0)

他有 NN 个引擎。每个引擎的使用方法和功能如下:

  • 使用第 ii 个引擎时,E869120 君当前位置的 XX 坐标会增加 xix_iYY 坐标会增加 yiy_i。也就是说,如果他当前在坐标 (X,Y)(X, Y),使用第 ii 个引擎后会移动到 (X+xi,Y+yi)(X + x_i, Y + y_i)
  • 引擎可以按任意顺序使用,但每个引擎最多只能使用一次。也可以选择不使用某些引擎。

他想要到达距离原点最远的位置。
请你求出他最后能到达的点 (X,Y)(X, Y) 到原点的距离 X2+Y2\sqrt{X^2 + Y^2} 的最大值。

输入格式

输入从标准输入读入,格式如下:

NN
x1x_1 y1y_1
x2x_2 y2y_2
\vdots
xNx_N yNy_N

输出格式

请输出他最后能到达的点到原点的距离的最大值,结果为实数。
只要你的答案与真实答案的相对误差或绝对误差在 101010^{-10} 以内,即视为正确。

输入输出样例

  • 输入#1

    3
    0 10
    5 -5
    -5 -5

    输出#1

    10.000000000000000000000000000000000000000000000000
  • 输入#2

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

    输出#2

    2.828427124746190097603377448419396157139343750753
  • 输入#3

    5
    1 1
    2 2
    3 3
    4 4
    5 5

    输出#3

    21.213203435596425732025330863145471178545078130654
  • 输入#4

    3
    0 0
    0 1
    1 0

    输出#4

    1.414213562373095048801688724209698078569671875376
  • 输入#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

说明/提示

限制条件

  • 1N1001 \leq N \leq 100
  • 1000000xi1000000-1\,000\,000 \leq x_i \leq 1\,000\,000
  • 1000000yi1000000-1\,000\,000 \leq y_i \leq 1\,000\,000
  • 输入均为整数

样例解释 1

如果合理使用引擎,最后能到达的点到原点的距离可以达到 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

样例解释 2

最后能到达的点到原点的最大距离是 22=2.828422\sqrt{2} = 2.82842\ldots
一种实现方法是:

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

样例解释 3

如果按顺序使用引擎 123451 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5,最终会到达 (15,15)(15, 15),距离原点为 152=21.213215\sqrt{2} = 21.2132\ldots

样例解释 4

也有可能存在 (xi,yi)=(0,0)(x_i, y_i) = (0, 0),即没有任何作用的引擎。

样例解释 5

请注意,也可能只有 11 个引擎。

样例解释 6

也可能只有 22 个引擎。

首页