CF2195H.Codeforces Heuristic Contest 001

There is a grid of $3n \times 3n$ points, consisting of all integer points $(x,y)$ such that $1 \le x,y \le 3n$.

Find a largest set of triangles satisfying the following conditions:

• Each triangle has its vertices on exactly three points on the grid.
• Each triangle has an area of exactly $\frac{1}{2}$. Note that they do not have to be right triangles.
• No two triangles share a common intersection point, including their vertices.

If there exist multiple largest such sets of triangles, you may output any of them.

存在一个 $3n \times 3n$ 的点阵，由所有满足 $1 \le x,y \le 3n$ 的整数点 $(x,y)$ 构成。

请找出满足以下条件的最大三角形集合：

• 每个三角形的三个顶点均取自该点阵中的三个点；
• 每个三角形的面积恰好为 $\frac{1}{2}$（它们不一定是直角三角形）；
• 任意两个三角形互不相交（包括顶点在内）。

若存在多个满足上述条件的最大三角形集合，输出其中任意一个即可。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 30$). The description of the test cases follows.

The only line of each test case contains a single integer $n$ ($1 \le n \le 166$).

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $166^2$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 30$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$1 \le n \le 166$）。

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

Output the maximum size $m$ of the set of triangles on one line ($0 \le m \le 3n^2$).

Then, output $m$ lines in the following format:

• $x_{i,1}\;y_{i,1}\;x_{i,2}\;y_{i,2}\;x_{i,3}\;y_{i,3}$: The vertices of the $i$-th triangle are $(x_{i,1},y_{i,1})$, $(x_{i,2},y_{i,2})$, $(x_{i,3},y_{i,3})$.

You may output the vertices of one triangle in any order (clockwise or counterclockwise).

Your output will be accepted if it satisfies all conditions and the maximum size given is correct.

输出位于同一条直线上的三角形集合的最大大小 $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})$。

每个三角形的三个顶点顺序可任意（顺时针或逆时针均可）。

只要您的输出满足所有条件，且所给出的最大大小 $m$ 正确，即视为可接受。

In the first test case, the example output has $2$ triangles as shown in the following image:

In the second test case, the example output has $12$ triangles as shown in the image on the left:

As the triangles are not required to be right triangles, the set of triangles shown in the image on the right will also be considered valid.

在第一个测试用例中，示例输出包含 $2$ 个三角形，如下图所示：

在第二个测试用例中，示例输出包含 $12$ 个三角形，如左侧图片所示：

由于题目不要求三角形必须为直角三角形，因此右侧图片中所示的三角形集合也被视为有效。