[AdditionalFile5594.zip](file://AdditionalFile5594.zip?type=additional_file)

#5594. 「PA 2017 Final」Wielokąt

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

题目译自 PA 2017 Final Wielokąt

在平面上绘制了 $n$ 条两两不相交的线段，每条线段都与直角坐标系的某个坐标轴平行。我们希望构造一个最多有 $20n$ 条边的多边形，其所有边都与坐标轴平行，并且其中有 $n$ 条边与这些给定的线段重合。

多边形的每两条连续的边都应相互垂直；多边形的边除了在连续两条边的公共顶点处相交外，不能有其他任何交点。输入的每条线段都必须是该多边形的一条边。所绘制线段的端点坐标是整数，但多边形顶点的坐标可以是小数。

输入格式

输入的第一行包含一个整数 $n$ $(1 \le n \le 100000)$，表示线段的数量。

接下来的 $n$ 行是线段的描述：每行包含四个整数 $x_1, y_1, x_2, y_2$ $(-10^8 \le x_1, y_1, x_2, y_2 \le 10^8)$，表示端点坐标为 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的线段。每条线段的长度都非零，并且要么是垂直的，要么是水平的。这些线段没有公共点。

输出格式

如果无法构造出满足题目条件的多边形，则在输出的唯一一行中输出 NIE。

否则，在输出的第一行输出一个数字 $m$ $(m \le 20n)$，表示多边形的边数。接下来的 $m$ 行应按照多边形周界上的顺序（方向任意）输出多边形的顶点：第 $i$ 行应包含两个数字 $x, y$ $(-10^9 \le x, y \le 10^9)$，表示第 $i$ 个顶点的坐标为 $(x, y)$。每个数字都必须以十进制形式给出，并且小数点后最多包含七位数字。

样例

输入

5
-1 1 -1 -1
0 0 0 -1
0 1 2 1
2 -1 2 0
0 2 -2 2

输出

22
-1 1
-1 -1
-0.6 -1
-0.6 0
-0.4 0
-0.4 -1
0 -1
0 0
1.4 0
1.4 -1
1.8 -1
1.8 0
2 0
2 -1
2.4 -1
2.4 2
2 2
2 1
0 1
0 2
-2 2
-2 1