CF2195H Codeforces Heuristic Contest 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$）。 保证所有测试用例中 $\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$ 个三角形，如下图所示：  在第二个测试用例中，示例输出展示了 $12$ 个三角形，见下左图：  由于三角形不要求为直角三角形，右图中的三角形集合同样是合法的。  由 ChatGPT 5 翻译