#P6802. [CEOI2020] 道路

[CEOI2020] 道路

题目背景

0.3s,32MB

题目描述

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

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

输入格式

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

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

输出格式

输出 N1N-1 行。

每行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,代表新修一条连接 (x1,y1)(x_1,y_1)(x2,y2)(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

提示

样例解释

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

子任务

所有数据均满足:2N1052 \leq N \leq 10^5107x1,y1,x2,y2107-10^7 \leq x_1,y_1,x_2,y_2 \leq 10^7

各子任务的约束条件如下:

子任务编号 分值 约束
11 00 样例
22 1515 输入的所有线段均为竖直线段
33 任意两条输入线段互相平行
44 输入的所有线段均为水平线段或竖直线段
55 N104N \leq 10^4
66 4040 无特殊约束

注意实际评测分值分配与上述约定不同。