题目描述

给定一个 $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$）。

保证所有测试用例中 $\sum n^2 \le 166^2$。

输出格式

对于每组测试用例，首先输出一行，包含一个整数 $m$，表示三角形集合的最大数量（$0 \le m \le 3n^2$）。

接下来输出 $m$ 行，每行 $6$ 个整数 $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$ 个三角形，见下左图：

由于三角形不要求为直角三角形，右图中的三角形集合同样是合法的。

由 ChatGPT 5 翻译

来源

Codeforces 2195H，英文题名 Codeforces Heuristic Contest 001。