P6948 [ICPC 2018 WF] Single Cut of Failure

入侵与犯罪预防公司 (the Intrusion and Crime Prevection Company, 简称 ICPC) 为家庭和商业公司建立了入侵检测系统。国际大学生编程竞赛 (the International Collegiate Programming Contest, 碰巧也简称 ICPC) 正在考虑雇佣该公司来确保下一年 World Finals 的题目文件的储藏房间的安全。 比赛工作人员希望防止过去几年发生的入侵尝试，例如在大楼的外部垂直速降然后从窗户进入，从排气管道爬进来，冒充 Bill Poucher （译者注：某知名计算机科学教授，ACM-ICPC 的执行董事），以及创造性地使用攻击潜艇。正因如此，题目文件将被储藏在仅有一扇门而没有任何其他出入口的房间里。 ICPC （指公司）建议在门的四边安装传感器，每对传感器由电线连接。如果有人打开了门，任何连接的一对传感器将检测到这个动作并引起警报声。 然而这个系统存在一个设计缺陷。入侵者可以在开门之前剪断这些电线。为了评估这个系统的安全性，你需要使用最少的线段剪断所有电线。下图展示了两种具有不同电线分布的门（对应于两个样例）以及最少的与所有电线相交的线段。 

第一行三个整数 $n, w, h$ 分别表示电线的数量 ($1 \le n \le 10^6$) 以及门的尺寸 ($1 \le w, h \le 10^8$) 。接下来 $n$ 行，每行描述一个电线的位置。这些行中每行包含四个整数 $x_1, y_1, x_2, y_2$ ($0 \le x_1, x_2 \le w, 0 \le y_1, y_2 \le h$) 表示该电线从 $(x_1, y_1)$ 连接到 $(x_2, y_2)$ 。每根电线连接门的不同的两边。没有电线连接到门的四个角落。输入的所有位置都是两两不同的。

输出最少的一组线段与所有电线有交。首先第一行输出线段的数量。然后逐行输出线段，每行以 $x_1$ $y_1$ $x_2$ $y_2$ 的格式给出一个从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的线段。每条线段的两个端点必须在门的不同的两边。线段的端点与任何电线端点及门的四个角落的距离不能小于 $10^{-6}$ 。 线段可以以任意顺序输出。线段的两个端点也可以以任意顺序输出。如果有多种可行的解，输出任意一组解即可。 译者注：线段的端点坐标可以是满足限制的任意**实数**。

Time limit: 6 s, Memory limit: 1024 MB.