A7596. [ABC139F] Engines
编程题
提高+/省选-
知识点
题目描述
E869120 君一开始站在二维平面上的原点 $(0, 0)$。
他有 $N$ 个引擎。每个引擎的使用方法和功能如下:
- 使用第 $i$ 个引擎时,E869120 君当前位置的 $X$ 坐标会增加 $x_i$,$Y$ 坐标会增加 $y_i$。也就是说,如果他当前在坐标 $(X, Y)$,使用第 $i$ 个引擎后会移动到 $(X + x_i, Y + y_i)$。
- 引擎可以按任意顺序使用,但每个引擎最多只能使用一次。也可以选择不使用某些引擎。
他想要到达距离原点最远的位置。
请你求出他最后能到达的点 $(X, Y)$ 到原点的距离 $\sqrt{X^2 + Y^2}$ 的最大值。
他有 $N$ 个引擎。每个引擎的使用方法和功能如下:
- 使用第 $i$ 个引擎时,E869120 君当前位置的 $X$ 坐标会增加 $x_i$,$Y$ 坐标会增加 $y_i$。也就是说,如果他当前在坐标 $(X, Y)$,使用第 $i$ 个引擎后会移动到 $(X + x_i, Y + y_i)$。
- 引擎可以按任意顺序使用,但每个引擎最多只能使用一次。也可以选择不使用某些引擎。
他想要到达距离原点最远的位置。
请你求出他最后能到达的点 $(X, Y)$ 到原点的距离 $\sqrt{X^2 + Y^2}$ 的最大值。
输入格式
输入从标准输入读入,格式如下:
> $N$
> $x_1$ $y_1$
> $x_2$ $y_2$
> $\vdots$
> $x_N$ $y_N$
> $N$
> $x_1$ $y_1$
> $x_2$ $y_2$
> $\vdots$
> $x_N$ $y_N$
输出格式
请输出他最后能到达的点到原点的距离的最大值,结果为实数。
只要你的答案与真实答案的相对误差或绝对误差在 $10^{-10}$ 以内,即视为正确。
只要你的答案与真实答案的相对误差或绝对误差在 $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 \leq N \leq 100$
- $-1\,000\,000 \leq x_i \leq 1\,000\,000$
- $-1\,000\,000 \leq y_i \leq 1\,000\,000$
- 输入均为整数
### 样例解释 1
如果合理使用引擎,最后能到达的点到原点的距离可以达到 $10$。有以下三种方法可以实现:
- 使用引擎 $1$,移动到 $(0, 10)$
- 先用引擎 $2$ 移动到 $(5, -5)$,再用引擎 $3$ 移动到 $(0, -10)$
- 先用引擎 $3$ 移动到 $(-5, -5)$,再用引擎 $2$ 移动到 $(0, -10)$
没有办法让距离超过 $10$,所以最大值为 $10$。
### 样例解释 2
最后能到达的点到原点的最大距离是 $2\sqrt{2} = 2.82842\ldots$。
一种实现方法是:
- 先用引擎 $1$ 移动到 $(1, 1)$,再用引擎 $2$ 移动到 $(2, 1)$,最后用引擎 $3$ 移动到 $(2, 2)$
### 样例解释 3
如果按顺序使用引擎 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$,最终会到达 $(15, 15)$,距离原点为 $15\sqrt{2} = 21.2132\ldots$。
### 样例解释 4
也有可能存在 $(x_i, y_i) = (0, 0)$,即没有任何作用的引擎。
### 样例解释 5
请注意,也可能只有 $1$ 个引擎。
### 样例解释 6
也可能只有 $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$
- 输入均为整数
### 样例解释 1
如果合理使用引擎,最后能到达的点到原点的距离可以达到 $10$。有以下三种方法可以实现:
- 使用引擎 $1$,移动到 $(0, 10)$
- 先用引擎 $2$ 移动到 $(5, -5)$,再用引擎 $3$ 移动到 $(0, -10)$
- 先用引擎 $3$ 移动到 $(-5, -5)$,再用引擎 $2$ 移动到 $(0, -10)$
没有办法让距离超过 $10$,所以最大值为 $10$。
### 样例解释 2
最后能到达的点到原点的最大距离是 $2\sqrt{2} = 2.82842\ldots$。
一种实现方法是:
- 先用引擎 $1$ 移动到 $(1, 1)$,再用引擎 $2$ 移动到 $(2, 1)$,最后用引擎 $3$ 移动到 $(2, 2)$
### 样例解释 3
如果按顺序使用引擎 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$,最终会到达 $(15, 15)$,距离原点为 $15\sqrt{2} = 21.2132\ldots$。
### 样例解释 4
也有可能存在 $(x_i, y_i) = (0, 0)$,即没有任何作用的引擎。
### 样例解释 5
请注意,也可能只有 $1$ 个引擎。
### 样例解释 6
也可能只有 $2$ 个引擎。