Roads
Contest: Central-European Olympiad in Informatics, CEOI 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated)
Difficulty rating: 2900
Tags: *special, geometry, sortings

The government of Treeland wants to build a new road network. There are $$$2N$$$ cities in Treeland. The unfinished plan of the road network already contains $$$N$$$ road segments, each of which connects two cities with a straight line. No two road segments have a common point (including their endpoints).  Your task is to determine $$$N-1$$$ additional road segments satisfying the following conditions:

1. Every new road segment must connect two cities with a straight line.
2. If two segments (new or old) have a common point, then this point must be an endpoint of both segments.
3. The road network connects all cities: for each pair of cities there is a path consisting of segments that connects the two cities.

Input format:
The first line of the standard input contains $$$N$$$ ($$${2 \leq N \leq 10^5}$$$) – the number of existing road segments. Each of the following $$$N$$$ lines contains four integers: $$$x_1,y_1, x_2, y_2$$$, where $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ are the coordinates of the endpoints of the segment $$$(-10^7 \leq x_i,y_i\leq 10^7)$$$.

Output format:
The standard output must contain $$$N-1$$$ lines, each of them containing four integers, $$$x_1, y_1, x_2, y_2$$$, where $$$(x_1,y_1)$$$ and $$$(x_2, y_2)$$$ are the coordinates of the cities that are the endpoints of a new road segment. If there are multiple solutions, your program may output any of them.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
Scoring:
$$$ \begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & 0 & \text{samples}\\ \hline 2 & 15 & \text{all input segments are vertical.} \\ \hline 3 & 15 & \text{each pair of input segments are parallel.} \\ \hline 4 & 15 & \text{each input segment is either horizontal or vertical.} \\ \hline 5 & 15 & N \le 10\,000 \\ \hline 6 & 40 & \text{no additional constraints}\\ \hline \end{array} $$$

Example input:
5
1 3 3 6
5 1 5 3
3 3 6 5
2 1 4 1
2 3 4 2

Example output:
2 1 1 3
2 3 2 1
3 3 2 3
5 1 4 2

Editorial:
We assume that for segment $$$s=(p,q)$$$ the relation $$$p.x<q.x$$$ or $$$p.x=q.x$$$ and $$$p.y<q.y$$$ holds, therefore we can say that $$$p$$$ is the left endpoint of the segment.  Consider the sequence of segment endpoints ordered by their x-coordinates.   We apply the sweep-line method, the event points of the sweeping are the x-coordinates of the endpoints.   For a given $$$sx$$$ coordinate let us denote by $$$Sl(sx)$$$ the set of segments intersecting the vertical line whose $$$x$$$ coordinate is $$$sx$$$. Elements of the set $$$Sl$$$ are ordered according to the $$$y$$$-coordinate of the intersection points. As the sweep progresses from left to right, if the point is a left endpoint, then it is inserted into $$$Sl$$$, and deleted if it is a right endpoint.
We add a sentinel, as the figure shows.
Each segment endpoint which is on the left of the sweep-line is already a node of the tree, the partial output.
For each segment $$$u \in Sl$$$ we compute a segment endpoint $$$Rmost(u)$$$, with the following property. Let $$$u \in Sl$$$ and $$$v \in Sl$$$ be segments such that $$$v$$$ is directly next to $$$u$$$ according to the ordering. Then for every point $$$q$$$ on the sweep-line located between the intersection points of $$$u$$$ and $$$v$$$, if the $$$\overline{Rmost(u), q}$$$ intersects any old or newly added segment then the intersection point must be an endpoint.
Therefore if we insert a left endpoint $$$q$$$ into $$$Sl$$$ then the segment $$$(Rmost(u), q)$$$ will be added to the solution.  Moreover, during both insertion and deletion we can update $$$Rmost(u)$$$ value in $$$O(log\, N)$$$ time if we represent the set $$$Sl$$$ by STL ordered set.  The running time of the whole algorithm is $$$O(N \log N)$$$.

Subtask 1
Constraint: All segments are vertical.  This subtask can be solved by sorting the segments and connecting consecutive segments' left and right endpoints. The sorting relation is easy to compute: $$$s_1=(p_1,q_1) < s_2=(p_2, q_2)$$$ iff $$$p_1.x<p_2.x$$$ or $$$p_1.x=p_2.x$$$ and $$$p_1.y< p_2.y$$$.
Subtask 2
Constraint: Each pair of segments are parallel.  This subtask also admits solution by sorting, but the computation of the sorting relation is not so easy. Namely, $$$s_1=(p_1,q_1) < s_2=(p_2, q_2)$$$ iff both $$$p_1$$$ and $$$q_1$$$ located on the left of the line determined by $$$s_2$$$ or $$$s_1$$$ and $$$s_2$$$ are colinear and $$$q_1$$$ is inbetween $$$p_2$$$ and $$$q_2$$$.
Subtask 3
Constraint: Each segment is either horizontal or vertical.   This subtask can be solved by a simplified implementation of the model solution algorithm, because it is easy to compute the sorting relation of the set $$$Sl$$$.
Subtask 4
Constraint: $$$N \le 10000$$$   There is an $$$O(N^2)$$$running time algorithm that can solve this subtask. For example if we represent the set $$$Sl(sx)$$$ by sorted array.