← 返回题目列表

Codeforces · 2195/H

H. Codeforces 启发式竞赛 001

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

有一个 $$$3n \times 3n$$$ 点的网格,由所有整数点 $$$(x,y)$$$ 组成,使得 $$$1 \le x,y \le 3n$$$。

查找 最大 满足以下条件的三角形集合:

  • 每个三角形的顶点都位于 正好三个 网格上的 点。
  • 每个三角形的面积正好为 $$$\frac{1}{2}$$$。请注意,他们 不 必须是直角三角形。
  • 没有两个三角形共享公共交点,包括它们的顶点。

如果存在多个最大的此类三角形集合,则可以输出其中任何一个。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 30$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 166$$$)。

保证所有测试用例的$$$n^2$$$总和不超过$$$166^2$$$。

输出

输出 最大 一条线上三角形集合的大小 $$$m$$$ ($$$0 \le m \le 3n^2$$$)。

然后,按以下格式输出 $$$m$$$ 行:

  • $$$x_{i,1}\;y_{i,1}\;x_{i,2}\;y_{i,2}\;x_{i,3}\;y_{i,3}$$$:第 $$$i$$$ 个三角形的顶点为 $$$(x_{i,1},y_{i,1})$$$, $$$(x_{i,2},y_{i,2})$$$,$$$(x_{i,3},y_{i,3})$$$。

您可以按任意顺序(顺时针或逆时针)输出一个三角形的顶点。

如果您的输出满足所有条件并且给定的最大尺寸正确,则您的输出将被接受。

示例

输入
复制

2
1
2

输出
复制

2
1 1 1 2 2 1
2 3 3 2 3 3
12
1 1 1 2 2 1
2 2 3 2 3 1
1 3 1 4 2 3
2 4 3 4 3 3
1 5 1 6 2 5
2 6 3 6 3 5
4 1 4 2 5 1
5 2 6 2 6 1
4 3 4 4 5 3
5 4 6 4 6 3
4 5 4 6 5 5
5 6 6 6 6 5

注意

在第一个测试用例中,示例输出具有 $$$2$$$ 三角形,如下图所示:

在第二个测试用例中,示例输出有 $$$12$$$ 三角形,如左图所示:

由于三角形不需要是直角三角形,因此右侧图像中显示的三角形组也将被视为有效。