← 返回题目列表

Codeforces · 1085/C

C. 连接三个

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

Squareland 国家森林被分为相等的 $$$1 \times 1$$$ 正方形地块,按南北和东西方向排列。每个图都可以通过其西南角的整数笛卡尔坐标 $$$(x, y)$$$ 来唯一描述。

三个朋友,爱丽丝、鲍勃和查理,打算在森林里购买三块不同的土地 $$$A、B、C$$$。最初,森林中的所有地块(包括地块 $$$A、B、C$$$)都被树木覆盖。朋友们想要互相拜访,所以他们想清理掉一些土地上的树木。清理后,人们应该能够通过相邻清理过的地块从任何其他地块到达 $$$A、B、C$$$ 中的任何一个地块。如果两个地块共享一条边,则它们是相邻的。

例如,$$$A=(0,0)$$$、$$$B=(1,1)$$$、$$$C=(2,2)$$$。要清除的最少地块数量为 $$$5$$$。其中一种方法以灰色显示。

当然,朋友们不想太紧张。帮助他们找出需要清理树木的最少面积。

输入

第一行包含两个整数 $$$x_A$$$ 和 $$$y_A$$$ — 绘图 $$$A$$$ 的坐标 ($$$0 \leq x_A, y_A \leq 1000$$$)。下面两行分别以相同的格式描述了图 $$$B$$$ 和 $$$C$$$ 的坐标 $$$(x_B, y_B)$$$ 和 $$$(x_C, y_C)$$$ ($$$0 \leq x_B, y_B, x_C, y_C \leq 1000$$$)。保证所有三个图都是不同的。

输出

在第一行打印一个整数 $$$k$$$ — 需要从树木中清除的最小地块数量。以下 $$$k$$$ 行应包含需要清理的所有地块的坐标。所有 $$$k$$$ 地块应该是不同的。您可以按任何顺序输出图。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

0 0
1 1
2 2

输出 #1

5
0 0
1 0
1 1
1 2
2 2

输入 #2

0 0
2 0
1 1

输出 #2

4
0 0
1 0
1 1
2 0

注意

第一个示例如图例所示。

第二个示例如下图所示: