题目描述

The Intrusion and Crime Prevention Company (ICPC) builds intrusion detection systems for homes and businesses. The International Collegiate Programming Contest (in a strange coincidence also known as ICPC) is considering hiring the company to secure the room that contains the problem set for next year's World Finals.

The contest staff wants to prevent the intrusion attempts that were made in past years, such as rappelling down the outside of the building to enter through a window, crawling through air ducts, impersonating Bill Poucher, and the creative use of an attack submarine. For that reason, the problems will be stored in a room that has a single door and no other exits.

ICPC (the company) proposes to install sensors on the four sides of the door, where pairs of sensors are connected by wires. If somebody opens the door, any connected sensor pair will detect this and cause an alarm to sound.

The system has one design flaw, however. An intruder might cut the wires before opening the door. To assess the security of the system, you need to determine the minimum number of line segments that cut all wires. Figure H.1 shows two configurations of wires on the door (corresponding to the two sample inputs), and minimum-size cuts that intersect all wires.

Figure H.1 : Illustrations of Sample Inputs $1$ and $2$ .

输入格式

The input starts with a line containing three integers $n , w$ , and $h$ , which represent the number of wires installed $(1 \le n \le 10^{6})$ and the dimensions of the door $(1 \le w , h \le 10^{8}).$ This is followed by $n$ lines, each describing a wire placement. Each of these lines contains four integers $x_{1}, y_{1}, x_{2},$ and $y_{2} (0 \le x_{1}, x_{2} \le w , 0 \le y_{1}, y_{2} \le h)$ , meaning that a wire goes from $(x_{1}, y_{1})$ to $(x_{2}, y_{2}).$ Each wire connects different sides of the door. No wire is anchored to any of the four corners of the door. All locations in the input are distinct.

输出格式

Display a minimum-size set of straight line cuts that intersect all wires. First, display the number of cuts needed. Then display the cuts, one per line in the format $x_{1} y_{1} x_{2} y_{2}$ for the cut between $(x_{1}, y_{1})$ and $(x_{2}, y_{2}).$ Each cut has to start and end on different sides of the door. Cuts cannot start or end closer than $10^{−6}$ to any wire anchor location or any corner of the door.

Cuts may be displayed in any order. The start and end locations of each cut may be displayed in either order. If there are multiple sets of cuts with the same minimum size, display any of them.

题目大意

题目描述

入侵与犯罪预防公司 (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}$ 。

线段可以以任意顺序输出。线段的两个端点也可以以任意顺序输出。如果有多种可行的解，输出任意一组解即可。

译者注：线段的端点坐标可以是满足限制的任意实数。

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

1
0 4 4 3

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

2
0 4 4 4.5
0 1 4 1

提示

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