← 返回题目列表

Codeforces · 1666/C

C. 连接点

中文机器翻译题面 查看原题

给定平面上的三个点。您应该在平面上选择一些与坐标轴平行的线段,以便所有三个点都连接起来。所选线段的总长度应尽可能最小。

如果存在一系列点 $$$p_0 = a, p_1, \ldots, p_k = b$$$ 使得点 $$$p_i$$$ 和 $$$p_{i+1}$$$ 位于同一线段上,则认为两个点 $$$a$$$ 和 $$$b$$$ 是相连的。

输入

输入由描述三个点的三行组成。每行包含两个由空格分隔的整数 $$$x$$$ 和 $$$y$$$ — 点的坐标 ($$$-10^9 \le x, y \le 10^9$$$)。这些点是成对不同的。

输出

在第一行输出 $$$n$$$ — 段数,最多 100。

接下来的 $$$n$$$ 行应包含段的描述。在一条线上输出四个整数$$$x_1$$$、$$$y_1$$$、$$$x_2$$$、$$$y_2$$$——对应线段端点的坐标($$$-10^9 \le x_1, y_1, x_2, y_2 \le 10^9$$$)。每个段应该是水平的或垂直的。

保证具有给定约束的解存在。

示例

输入
复制

1 1
3 5
8 6

输出
复制

3
1 1 1 5
1 5 8 5
8 5 8 6

注意

示例中的点和线段如下所示。