多項式圓弧算法？

Question

在課堂上，我們看到了下面的問題，但我沒有解決問題。有沒有人可以解釋我更詳細的程序來解決這個問題或給我一個更好的解決方案？：

假設在飛機上的n個點是給定的。找到一個有n-1個邊的多邊形圓弧，其頂點給定點，其邊不相交（相鄰邊可以形成180°角）。操作的次數應該是n log n。

老師溶液：

排序所有相對於該點的x座標;當x座標相等時，考慮y座標，然後按照線段連接所有頂點（按此順序）。

Answer 1

老師的解決方案是（幸運的）好。我會盡力爲你想象這個。

只需在圖上繪製點。然後，您可以從最左側的點到下一個點畫一條線。這樣，將所有點連接到右側。

如果所有的點都具有不同的x座標，這將制定出，並沒有線將穿越：

對於具有相同x座標的點，我們先去最低（最小的y座標），然後上升。沒有穿過那裏，要麼。