AtCoder Beginner Contest 139
翻译中…
Problem Statement
翻译中…
E869120 is initially standing at the origin $(0, 0)$ in a two-dimensional plane.
翻译中…
He has $N$ engines, which can be used as follows:
翻译中…
- When E869120 uses the
$i$-th engine, his$X$- and$Y$-coordinate change by$x_i$and$y_i$, respectively. In other words, if E869120 uses the$i$-th engine from coordinates$(X, Y)$, he will move to the coordinates$(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)$ be his final coordinates. Find the maximum possible value of $\sqrt{X^2 + Y^2}$, the distance from the origin.
翻译中…
Constraints
翻译中…
$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$- All values in input are integers.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N
x_1 y_1
x_2 y_2
: :
x_N y_N翻译中…
Output
翻译中…
Print the maximum possible final distance from the origin, as a real value. Your output is considered correct when the relative or absolute error from the true answer is at most $10^{-10}$.
翻译中…
样例
Input #1
3
0 10
5 -5
-5 -5
Output #1
10.000000000000000000000000000000000000000000000000
The final distance from the origin can be $10$ if we use the engines in one of the following three ways:
- Use Engine $1$ to move to $(0, 10)$.
- Use Engine $2$ to move to $(5, -5)$, and then use Engine $3$ to move to $(0, -10)$.
- Use Engine $3$ to move to $(-5, -5)$, and then use Engine $2$ to move to $(0, -10)$.
The distance cannot be greater than $10$, so the maximum possible distance is $10$.
Input #2
5
1 1
1 0
0 1
-1 0
0 -1
Output #2
2.828427124746190097603377448419396157139343750753
The maximum possible final distance is $2 \sqrt{2} = 2.82842...$. One of the ways to achieve it is:
- Use Engine $1$ to move to $(1, 1)$, and then use Engine $2$ to move to $(2, 1)$, and finally use Engine $3$ to move to $(2, 2)$.
Input #3
5
1 1
2 2
3 3
4 4
5 5
Output #3
21.213203435596425732025330863145471178545078130654
If we use all the engines in the order $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$, we will end up at $(15, 15)$, with the distance $15 \sqrt{2} = 21.2132...$ from the origin.
Input #4
3
0 0
0 1
1 0
Output #4
1.414213562373095048801688724209698078569671875376
There can be useless engines with $(x_i, y_i) = (0, 0)$.
Input #5
1
90447 91000
Output #5
128303.000000000000000000000000000000000000000000000000
Note that there can be only one engine.
Input #6
2
96000 -72000
-72000 54000
Output #6
120000.000000000000000000000000000000000000000000000000
There can be only two engines, too.
Input #7
10
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
Output #7
148.660687473185055226120082139313966514489855137208
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。