搬运自官方题解，由 ChatGPT 5.2 翻译，旨在给出比原有的唯一一篇题解更给人读的题解。

Line（回顾）

在这个问题中，我们在二维平面上给定了 $n$ 个点，这些点的 $x$ 坐标和 $y$ 坐标两两不同。我们的任务是从原点出发，构造一条折线，使其经过（覆盖）所有给定的点。

$2n$ 段的解法

一个很容易想到的解法是：对每个点使用两条线段来覆盖它（例如：先走到正确的 $x$ 坐标，再走到正确的 $y$ 坐标）。 这种方法一共使用 $2n$ 条线段，可以获得 $12$ 分。

螺旋（Spiral）

考虑最左、最上、最右和最下的点。它们形成了一个包围盒（bounding box），我们可以用 $4$ 条线段覆盖这个包围盒。然后将这些点移除，继续处理一个更小的子问题。 为了连接不同层的包围盒，我们可以从内层包围盒继续延伸折线，并朝着外层包围盒的合适方向前进。 这种解法根据实现不同，大约可以获得 $50$ 分左右。

链（Chain）

注意到：如果一组点形成一条“链”（例如 $x$ 和 $y$ 坐标同时递增），我们可以在不浪费任何线段的情况下覆盖它们。

根据 Dilworth 定理，在一个长度为 $k$ 的序列中，一定存在一个长度至少为 $\sqrt{k}$ 的递增序列或递减序列。我们可以在 $O(k \log k)$ 时间内找到这样的序列。 此外，我们还能将整个序列分解为大约 $\sqrt{k}$ 条递增和递减的序列。

因此在本问题中，我们可以构造大约 $\sqrt{n}$ 条链，并用额外的 $\sqrt{n}$ 条线段将它们连接起来。 这种解法一共使用

条线段，大约可以获得 $60$ 分。

$n+6$ 的解法

我们重新考虑螺旋方法。只有当包围盒中少于 $4$ 个点时，才会浪费额外的线段（例如有一个点同时是最左和最上的点）。

我们可以将这些点移除，并放入两条链中：

• 一条从左上角走到右下角；
• 另一条从右上角走到左下角。

算法如下：

• 如果一个包围盒中恰好有 $4$ 个点，则将它们加入螺旋中并移除；
• 否则，找到一个同时位于包围盒两条边上的点，将它加入到合适的链中并移除。

这样我们最终得到三个对象：一个螺旋和两条链。我们最多只需要再用 $2$ 条线段，就可以将它们彼此以及与原点连接起来。 这种解法大约可以获得 $95$ 分。

$n+3$ 的解法

为了得到更好的结果，我们还需要加入一些小技巧，包括：

• 考虑所有可能的连接顺序；
• 考虑遍历这些对象时的不同方向。

通过这些优化，可以得到一个使用

条线段的解法，从而获得满分 $100$ 分。