边数至少为 $2n-2$，因此答案至少为 $2n-1$。将所有点按 $x$ 为第一关键字，$y$ 为第二关键字排序后，相邻两个点之间的 $n-1$ 条线段不会在端点之外的点相交。先从前往后连，再从后往前连即可取到下界。
时间复杂度：$O(n\log n)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
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.