← 返回题目列表

Codeforces · 1402/B

B. 道路

中文机器翻译题面 查看原题

Treeland 政府希望建设一个新的道路网。 Treeland 有 $$$2N$$$ 城市。未完成的路网规划已包含$$$N$$$路段,每条路段均以直线连接两个城市。没有两个路段有公共点(包括它们的端点)。 您的任务是确定满足以下条件的 $$$N-1$$$ 附加路段:

1. 每个新路段必须以直线连接两个城市。
2. 如果两个线段(新的或旧的)有一个公共点,则该点必须是两个线段的端点。
3. 道路网连接所有城市:对于每对城市,都有一条由连接这两个城市的路段组成的路径。

输入

标准输入的第一行包含 $$$N$$$ ($$${2 \leq N \leq 10^5}$$$) – 现有路段的数量。以下 $$$N$$$ 行中的每一行都包含四个整数:$$$x_1,y_1, x_2, y_2$$$,其中 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 是线段 $$$(-10^7 \leq x_i,y_i\leq 10^7)$$$ 的端点坐标。

输出

标准输出必须包含 $$$N-1$$$ 行,每行包含四个整数 $$$x_1, y_1, x_2, y_2$$$,其中 $$$(x_1,y_1)$$$ 和 $$$(x_2, y_2)$$$ 是作为新路段端点的城市的坐标。如果有多个解决方案,您的程序可能会输出其中任何一个。

示例

输入 #1

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

输出 #1

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

注意

评分:
$$$ \begin{array}{|c|c|l|} \hline \text{子任务} & \text{Points} & \text{约束} \\ \hline 1 & 0 & \text{samples}\\ \hline 2 & 15 & \text{所有输入段都是垂直的。} \\ \hline 3 & 15 & \text{每对输入段都是平行的。} \\ \hline 4 & 15 & \text{每个输入段是水平或垂直的。} \\ \hline 5 & 15 & N \le 10\,000 \\ \hline 6 & 40 & \text{无附加约束}\\ \hline \end{array} $$$