P4125 [WC2012] Metasequoia in Memory

Changzhou Senior High School of Jiangsu is a century-old prestigious school, filled with countless unforgettable memories. Will remembers that when he was little, before the school's reconstruction, there was a tall metasequoia grove. When the metasequoias shed their leaves, the needles would cover the ground like a blanket, making it romantic and leisurely to walk on. Back then, Will and his classmates liked to use these needles to play a “taking needles” game under the metasequoias. At the start of the game, everyone lays $n$ needles flat on the ground. Then, in each round, one player may choose one needle and move it in the horizontal or vertical direction (that is, translate it to infinity) — provided that during the movement it is not blocked by any needle that has not yet been moved away. If a needle’s movement would be blocked in a round, then this move is illegal and not allowed. After $n$ rounds, when all needles have been removed, the game ends. Not every needle can be moved at any time. When there are many needles, determining in each round whether a specific needle can be moved in a given direction is troublesome. Now we abstract the ground as a 2D Cartesian plane, the $n$ needles as $n$ pairwise disjoint line segments in the plane, labeled from $1$ to $n$. Will also provides, for each round, the index of the needle he wants to move and the direction. Please help him: 1. Find in which round the earliest illegal move occurs. 2. Provide a legal move sequence that completes the game. Note: When moving segments, merely touching at endpoints does not cause obstruction. See the sample for details.

The first line contains a positive integer $n$, the number of needles. The next $n$ lines each contain $4$ integers describing the positions of the needles. On the $i$-th of these lines, the integers $a_i$, $b_i$, $c_i$, $d_i$ indicate that the endpoints of the line segment abstracting needle $i$ are $(a_i, b_i)$ and $(c_i, d_i)$. The next $n$ lines each contain $2$ integers describing the moves. On the $i$-th of these lines, the integers $p_i$, $q_i$ indicate that in round $i$, the needle to move is $p_i$, and the direction is $q_i$. Here $q_i$ is an integer between $0$ and $3$: $0$ means move left (the negative $x$-axis direction), $1$ means move up (the positive $y$-axis direction), $2$ means move right, and $3$ means move down. The input is guaranteed that: - All segments have positive length, no two segments share a point, and there are no vertical or horizontal segments. - $p_1$ through $p_n$ form a permutation of $1$ through $n$. - There is at least one illegal move in Will’s given sequence. - There always exists a sequence of $n$ legal moves that completes the game.

The output contains $n+1$ lines. The first line contains an integer between $1$ and $n$, indicating the earliest round in which an illegal move occurs. The next $n$ lines each contain two integers, as in the input format, describing a legal move sequence.

[Sample explanation] In round $3$ of Will’s given plan, moving needle $4$ to the left is blocked by needle $5$. [Constraints] See the table below.  For a test point: - If the illegal move detection is correct but the provided plan is wrong, you can get $5$ points. The message will be: `An invalid move in step`. - If the illegal move detection is wrong but the provided plan is correct, you can get $5$ points. The message will be: `Negative error detection!`. - If both the detection and the plan are correct, you get $10$ points; otherwise, $0$ points. If the program’s output format is incorrect, it will be directly judged as $0$ points. Translated by ChatGPT 5