In this problem, we are given ~n~ dots in a 2D-plane with distinct ~x~ coordinates and ~y~ coordinates. Our task is to construct a broken line starting from the origin that will cover all dots.

~2n~ solution

An easy solution is to use ~2~ segments to cover each dot (for example: first set the ~x~ coordinate, then ~y~ coordinate). This solution uses ~2n~ segments and receives ~12~ points.

Spiral

Let us consider the left-most, top-most, right-most and bottom-most dot. They create a bounding box which we can cover with ~4~ segments. We can remove these points and continue with a smaller problem. To connect the bounding boxes, we can just continue the line from the inner bounding box and go toward the proper direction in the outer box. This solution receives about ~50~ points, depending on the implementation.

Chain

Let us notice that we can cover a chain of points (for example with increasing ~x~ and ~y~ values) without wasting any segment. From Dilworth's theorem, we know that in the sequence of length ~k~, there exists an increasing sequence or decreasing sequence of length ~\sqrt k~. We can find this sequence in ~\mathcal O(k \log k)~. Moreover, we can decompose the whole sequence into ~\sqrt k \log k~ increasing and decreasing sequences. Therefore in our problem, we can create ~\sqrt n \log n~ chains and connect them with ~\sqrt k \log k~ additional segments. This solution uses ~n + 2 \sqrt n \log n~ segments and receives about ~60~ points.

~n+6~ solution

Let us reconsider the spiral. We waste additional segments only if the bounding box contains less than ~4~ points (for example there's a point that is both the left-most and the top-most one). We can remove these points and put them in one of two chains (one going from the top-left corner to the bottom-right corner) and one going from the top-right corner to the bottom-left one).

The algorithm is as follows:

• if a bounding box has ~4~ points in it, add them to the spiral, and remove these points,
• otherwise, find a point that lies on two sides of the bounding box, add it to the proper chain and remove it.

Then we have three objects (spiral and two chains) and we can use up to ~2~ segments to connect them to themselves and the origin. This solution gets about ~95~ points.

~n+3~ solution

To come up with an even better solution, we need to add some small tricks, including considering all possible orders in which we can connect these objects and directions in which we can traverse them. These optimizations lead a solution with ~n+3~ segments, which gets ~100~ points.