2
$\begingroup$

There are $n$ vectors, represented as $(d_x, d_y)$ pairs. Someone stands at point $(0, 0)$ of infinite euclidean grid. For every vector he can either move by $d_x$ in $x$ axis and $d_y$ in $y$ axis or ignore the vector and don't move at all. Each vector can be used at most once. He wants to get as far away from $(0, 0)$ as possible. What is the maximum distance from $(0, 0)$ which he can achieve?

For example:

$n = 5$, vectors: $\lbrace (2, -2), (-2, -2), (0, 2), (3, 1), (-3, 1)\rbrace$.

Result: $\sqrt{26} \approx 5.099$ (when $(0, 2), (3, 1)$ and $(2, -2)$ are used, as shown in the picture. Another equally good solution uses $(0, 2), (−3, 1)$ and $(−2, −2)$).

Illustration for example

How can this problem be solved in $O(n \log n)$ time?

$\endgroup$
0

0