ICPC 2018 · Problem H · Single Cut of Failure

Time limit: 6 seconds

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

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

Input

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 x1, x2 \le w$, $0 \le y1, y2 \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.

ACM-ICPC World Finals 2018 Problem H: Single Cut of Failure

Output

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 $x1 y1 x2 y2$ 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.

Sample Input 1

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

Sample Output 1

1
0 4 4 3

Sample Input 2

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

Sample Output 2

2
0 4 4 4.5
0 1 4 1

ACM-ICPC World Finals 2018 Problem H: Single Cut of Failure