P9397 「DBOI」Round 1 DTTM

张则雨和穆制程坐在天台上看着满天的星辰。在他们的世界，流行一种连接星星的活动。他们对此有一种浪漫的诠释：如果连不完，剩下的一颗星星就是身旁的人；如果连得完，那身边的人和自己都是星星。

星空中有 $n$ 颗星星，第 $i$ 颗位于坐标 $(x_i,y_i)$。你需要把星星连接成满足张则雨的如下需求： - 每一颗星星都是且仅是一条线段的端点，所有线段互不相交（包括端点）。 - 所有线段左右端点 $|x_l-x_r|$ 之和有最小值。 然而张则雨有点笨，并不知道应该怎么连。穆制程知道你是地球上最聪明的人，于是告诉你 $n$ 颗星星的坐标，你需要输出连接方案或者报告无解。

无

无

样例 1 的方案如图：  样例 2 的方案如图：  **本题使用捆绑测试与子任务依赖。** | $\rm Subtask$ | $n\leqslant$ | $(x,y)$ | 特殊性质 | 得分 | 子任务依赖 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $0\leqslant x,y\leqslant 20$ | 无 | $10$ | 无 | | $2$ | $10^3$ | $0\leqslant x,y\leqslant10^3$ | 无 | $15$ | $1$ | | $3$ | $10^3$ | $0\leqslant x,y\leqslant10^9$ | 无 | $15$ | $1,2$ | | $4$ | $5\times10^5$ |$-10^9\leqslant x,y\leqslant10^9$ | $A$ | $5$ | 无 | | $5$ | $5\times10^5$ | $-10^3\leqslant x,y\leqslant10^3$ | 无 | $20$ | $1,2$ | $6$ | $5\times10^5$ | $-10^9\leqslant x,y\leqslant10^9$ | 无 | $35$ | $1,2,3,4,5$ 特殊性质 $A$：满足所有 $x_i$ 都相等。 保证对于 $100\%$ 的数据，$1\leqslant n\leqslant5\times 10^5$，$0\leqslant|x|,|y|\leqslant 10^9$ 且对于任意 $i\ne j$，有 $(x_i,y_i)\neq (x_j,y_j)$。