algorithm - 多项式弧算法？

Question

在课堂上，我们看到了以下问题，但我不明白解决方案。有人可以更详细地向我解释解决此问题的过程或给我更好的解决方案吗？：

假设给定平面上的 n 个点。找到一个多边形弧，它的顶点是给定的点，并且边不相交。（相邻边可以形成 180 角）。操作的数量应该是 n log n 的顺序。

老师的解决方法是：

相对于 x 坐标对所有点进行排序；当 x 坐标相等时，考虑 y 坐标，然后通过线段（按此顺序）连接所有顶点。

Answer 1

你老师的解决方案（幸运的是）很好。我会试着为你想象一下。

只需在绘图上绘制点即可。然后你可以从最左边的点到下一个点画一条线。这样，连接所有向右的点。

如果所有的点都有不同的 x 坐标，那就可以解决，并且没有线会交叉：

对于x坐标相同的点，我们先到最低点（最小的y坐标）再往上走。那里也没有过路。