AT_abc139_f.[ABC139F] Engines
提高+/省选-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
E869120 君一开始站在二维平面上的原点 (0,0)。
他有 N 个引擎。每个引擎的使用方法和功能如下:
- 使用第 i 个引擎时,E869120 君当前位置的 X 坐标会增加 xi,Y 坐标会增加 yi。也就是说,如果他当前在坐标 (X,Y),使用第 i 个引擎后会移动到 (X+xi,Y+yi)。
- 引擎可以按任意顺序使用,但每个引擎最多只能使用一次。也可以选择不使用某些引擎。
他想要到达距离原点最远的位置。
请你求出他最后能到达的点 (X,Y) 到原点的距离 X2+Y2 的最大值。
输入格式
输入从标准输入读入,格式如下:
N
x1 y1
x2 y2
⋮
xN yN
输出格式
请输出他最后能到达的点到原点的距离的最大值,结果为实数。
只要你的答案与真实答案的相对误差或绝对误差在 10−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
说明/提示
限制条件
- 1≤N≤100
- −1000000≤xi≤1000000
- −1000000≤yi≤1000000
- 输入均为整数
样例解释 1
如果合理使用引擎,最后能到达的点到原点的距离可以达到 10。有以下三种方法可以实现:
- 使用引擎 1,移动到 (0,10)
- 先用引擎 2 移动到 (5,−5),再用引擎 3 移动到 (0,−10)
- 先用引擎 3 移动到 (−5,−5),再用引擎 2 移动到 (0,−10)
没有办法让距离超过 10,所以最大值为 10。
样例解释 2
最后能到达的点到原点的最大距离是 22=2.82842…。
一种实现方法是:
- 先用引擎 1 移动到 (1,1),再用引擎 2 移动到 (2,1),最后用引擎 3 移动到 (2,2)
样例解释 3
如果按顺序使用引擎 1→2→3→4→5,最终会到达 (15,15),距离原点为 152=21.2132…。
样例解释 4
也有可能存在 (xi,yi)=(0,0),即没有任何作用的引擎。
样例解释 5
请注意,也可能只有 1 个引擎。
样例解释 6
也可能只有 2 个引擎。