P6802 [CEOI 2020] 道路
题目背景
0.3s，32MB
题目描述
Treeland 政府准备建立一个全新的道路网。Treeland 共有 $2N$ 个城市，目前已经修建了 $N$ 条道路，每条道路都是一条连接两个城市的线段。这 $N$ 条道路两两没有交点（包括端点处）。你现在需要再修建 $N-1$ 条道路，要求：
1. 每条道路都是一条连接两个城市的线段。
2. 道路只能在端点处相交。
3. 对于任意两个城市，均能通过该路网相互抵达。
输入格式
无
输出格式
无
说明/提示
### 样例解释
下图中，实线表示已经修建的道路，虚线代表新修道路。
### 子任务
所有数据均满足：$2 \leq N \leq 10^5$，$-10^7 \leq x_1,y_1,x_2,y_2 \leq 10^7$。
各子任务的约束条件如下：
| 子任务编号 | 分值 | 约束 |
| ---------- | ---- | ------------------------------------ |
| $1$ | $0$ | 样例 |
| $2$ | $15$ | 输入的所有线段均为竖直线段 |
| $3$ | $15$ | 任意两条输入线段互相平行 |
| $4$ | $15$ | 输入的所有线段均为水平线段或竖直线段 |
| $5$ | $15$ | $N \leq 10^4$ |
| $6$ | $40$ | 无特殊约束 |
注意实际评测分值分配与上述约定不同。