Problem Description

Recently, Xiao Cong, in order to forget the noise of the city, came to Stardew Valley to start farming and make a fortune. However, because Xiao Cong spent all the money on gacha draws, there was not enough money to buy seeds. To collect enough money to raise pigs, Xiao Cong has to start a large-scale search for wild vegetables.

Stardew Valley is an infinite two-dimensional plane, and you can move freely on this plane. Xiao Cong may find wild vegetables on $n$ line segments on this plane, but these segments are directed. Xiao Cong must move along the direction of a segment in order to find wild vegetables. To find more wild vegetables, Xiao Cong wants to walk through all places where wild vegetables may appear in Stardew Valley. In other words, for each segment, Xiao Cong needs to traverse every point on that segment along its direction. Of course, Xiao Cong may choose to traverse a segment in multiple parts. More specifically, Xiao Cong may leave the segment at any position and enter the segment again at any position, as long as the union of the traveled paths covers this directed segment.

Xiao Cong wants to find a path as short as possible. This path should consist of $m$ line segments and cover the $n$ directed segments in Stardew Valley. Xiao Cong may choose any point in Stardew Valley as the starting point of the path, and it must also be the ending point, i.e. Xiao Cong must finally return to the starting position.

Now, Xiao Cong needs to write a Connect Four (Si Zi Qi) course assignment, and does not know how to plan the walking route to make the moving distance as short as possible, so this difficult task is handed to you, the smart one.

Note: If two segments partially overlap and have the same direction, then when you walk through the overlapping part, we consider that this part of both segments has been traversed.

Input Format

The first line contains an integer $n$, representing the number of directed segments.

The next $n$ lines each contain four integers $x_1, y_1, x_2, y_2$, meaning this segment is a directed segment from $(x_1, y_1)$ to $(x_2, y_2)$.

Output Format

The first line should contain an integer $m$, representing the number of points in the polyline path traveled by Xiao Cong, and it must satisfy $m\le\min(5n^2,5\times 10^6)$. Then output $m$ lines, listing the points on the path in order. Each line should contain two floating-point numbers $x, y$ describing the $x$- and $y$-coordinates of a point. Here, $x, y$ should be kept to no more than $5$ digits after the decimal point.

3
0 0 0 100
0 100 100 100
100 100 0 0

4
0 0
0 100
100 100
0 0

3
0 0 0 100
1 51 1 49
0 100 0 0

5
0 0
0 100
1 51
1 49
0 100

Hint

This is an output-only problem. The input and checker will be provided in the attachments.

For each testdata, if your output format does not meet the requirements, or if the path you output does not traverse all the given $n$ directed segments, then this test point gets $0$ points. Otherwise, we will compute the length $d$ of your path, and calculate your score using $10$ scoring parameters $a_1\ge a_2\ge...\ge a_{10}$:

The data guarantees that $a_1$ is large enough to ensure that a valid solution can get at least $1$ point.

Sample Explanation

For sample $1$, Xiao Cong moved a total distance of $200+100\sqrt2$, which is also the optimal solution for this sample.

For sample $2$, in this solution, Xiao Cong moved a total distance of $202+\sqrt{2402}+\sqrt{2602}$, but this is not the optimal solution for this testdata.

Translated by ChatGPT 5