← 返回题目列表

Codeforces · 68/E

E. 联系方式

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

小彼佳正在为与外星人的第一次接触做准备。他知道外星飞船的形状是非简并三角形,并且恰好有 4 艘。船舶的着陆平台可以由位于笛卡尔平面的某些点的 3 个特殊的柱组成,使得这 3 个点形成一个在旋转、平移(沿某个向量的平行移动)和反射(沿边缘对称)方面等于船舶的三角形。登陆后船只可以重叠。

每个纵队可以用来登陆多艘船,例如,如果有两艘相等的船,我们不需要建造6个纵队来登陆两艘船,3个就足够了。佩蒂亚想知道最少需要多少纵队才能让所有船只登陆。

输入

4 行中的每行将包含 6 个整数 x1 y1 x2 y2 x3 y3 (0 ≤ x1, y1, x2, y2, x3, y3 ≤ 20),代表描述 4 艘船中每艘船形状的 3 个点。保证每条线上的 3 个点代表一个非退化三角形。

输出

第一行应包含足以着陆所有宇宙飞船的最小列数。

示例

输入 #1

0 0 1 0 1 2
0 0 0 2 2 2
0 0 3 0 1 2
0 0 3 0 2 2

输出 #1

4

输入 #2

0 0 0 1 1 1
0 0 0 2 2 2
0 0 0 5 5 5
0 0 0 17 17 17

输出 #2

9

注意

在第一个测试用例中,列可以放入以下点:(0, 0)、(1, 0)、(3, 0)、(1, 2)。请注意,第二艘船可以使用最后 3 列着陆。

在第二个测试用例中,可以选择以下点:(0, 0)、(0, 1)、(1, 0)、(0, 2)、(2, 0)、(0, 5)、(5, 0)、(0, 17)、(17, 0)。不可能使用少于 9 列。