#3349. 「CEOI2020」道路

内存限制:256 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: StudyingFather

题目描述

题目译自 CEOI 2020 Day1 T2「Roads

Treeland 政府准备建立一个全新的道路网。Treeland 共有 2N 个城市,目前已经修建了 N 条道路,每条道路都是一条连接两个城市的线段。这 N 条道路两两没有交点(包括端点处)。你现在需要再修建 N-1 条道路,要求:

  1. 每条道路都是一条连接两个城市的线段。
  2. 道路只能在端点处相交。
  3. 对于任意两个城市,均能通过该路网相互抵达。

输入格式

输入第一行包含一个整数 N

接下来 N 行,每行包含四个整数 x_1,y_1,x_2,y_2 ,表示 (x_1,y_1) (x_2,y_2) 两座城市间存在一条道路直接相连。

输出格式

输出 N-1 行。

每行包含四个整数 x_1,y_1,x_2,y_2 ,代表新修一条连接 (x_1,y_1) (x_2,y_2) 两座城市间的道路。

如果存在多种方案,任意输出一种即可。

样例

样例输入

5
1 3 3 6
5 1 5 3
3 3 6 5
2 1 4 1
2 3 4 2

样例输出

2 1 1 3
2 3 2 1
3 3 2 3
5 1 4 2

样例解释

下图中,实线表示已经修建的道路,虚线代表新修道路。

roads.png

数据范围与提示

所有数据均满足: 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 无特殊约束