边数至少为 $2n-2$，因此答案至少为 $2n-1$。将所有点按 $x$ 为第一关键字，$y$ 为第二关键字排序后，相邻两个点之间的 $n-1$ 条线段不会在端点之外的点相交。先从前往后连，再从后往前连即可取到下界。
时间复杂度：$O(n\log n)$。
QOJ.ac
QOJ
Discussion #345 for Problem #3309. Sewing Graph
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:13:28
Last updated: 2025-12-14 07:13:30
题解
Comments
No comments yet.