Description

There are $n$ pieces of cheese in a room. A little mouse wants to eat them all. What is the minimum distance it must run? The mouse starts at point $(0, 0)$.

Input Format

The first line contains an integer $n$, the number of pieces of cheese.

Lines $2$ to $(n + 1)$ each contain two real numbers. The real numbers on the $(i + 1)$-th line represent the coordinates $x_i, y_i$ of the $i$-th piece of cheese.

Output Format

Output a single real number: the minimum distance required, with $2$ decimal places.

4
1 1
1 -1
-1 1
-1 -1

7.41

Hint

• Constraints

For all test points, it is guaranteed that $1 \leq n \leq 15$, $|x_i|, |y_i| \leq 200$, and there are at most $3$ digits after the decimal point.

• Hint

For two points $(x_1, y_1)$ and $(x_2, y_2)$, the distance formula is $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$.

$2022.7.13$: A new set of $\text{Hack}$ testdata has been added.

Translated by ChatGPT 5