P6802 [CEOI 2020] Roads

0.3 s, 32 MB

The government of Treeland plans to build a brand-new road network. Treeland has a total of $2N$ cities. Currently, $N$ roads have already been built, and each road is a line segment connecting two cities. These $N$ roads do not intersect each other in pairs (including at endpoints). You now need to build another $N-1$ roads, such that: 1. Each road is a line segment connecting two cities. 2. Roads may intersect only at endpoints. 3. For any two cities, it must be possible to travel between them using this road network.

The first line contains an integer $N$. The next $N$ lines each contain four integers $x_1, y_1, x_2, y_2$, indicating that there is a road directly connecting the two cities at $(x_1, y_1)$ and $(x_2, y_2)$.

Output $N-1$ lines. Each line contains four integers $x_1, y_1, x_2, y_2$, representing a newly built road connecting the two cities at $(x_1, y_1)$ and $(x_2, y_2)$. If there are multiple solutions, output any one.

### Sample Explanation In the figure below, solid lines are roads that have already been built, and dashed lines are new roads.  ### Subtasks All testdata satisfy: $2 \leq N \leq 10^5$, $-10^7 \leq x_1, y_1, x_2, y_2 \leq 10^7$. The constraints for each subtask are as follows: | Subtask ID | Score | Constraints | | ---------- | ----- | ------------------------------------ | | $1$ | $0$ | Sample | | $2$ | $15$ | All input segments are vertical | | $3$ | $15$ | Any two input segments are parallel | | $4$ | $15$ | All input segments are horizontal or vertical | | $5$ | $15$ | $N \leq 10^4$ | | $6$ | $40$ | No special constraints | Note that the actual scoring distribution in the judge is different from the agreement above. Translated by ChatGPT 5