A16715. Codeforces Heuristic Contest 001
编程题
提高+/省选-
知识点
题目描述
给定一个 $3n \times 3n$ 的点阵，包含所有整数点 $(x, y)$，满足 $1 \le x, y \le 3n$。
请找出一个最大集合的三角形，需满足以下条件：
- 每个三角形的三个顶点都在格点上，且恰好有三个不同的顶点。
- 每个三角形的面积恰好为 $\frac{1}{2}$。注意三角形不一定要求为直角三角形。
- 任意两个三角形都没有公共的交点，包括顶点。
如果存在多个规模最大的三角形集合，你可以输出其中任意一个。
请找出一个最大集合的三角形，需满足以下条件：
- 每个三角形的三个顶点都在格点上，且恰好有三个不同的顶点。
- 每个三角形的面积恰好为 $\frac{1}{2}$。注意三角形不一定要求为直角三角形。
- 任意两个三角形都没有公共的交点，包括顶点。
如果存在多个规模最大的三角形集合，你可以输出其中任意一个。
输入格式
每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 30$），表示测试用例的组数。
接下来每组测试用例占一行，包含一个整数 $n$（$1 \le n \le 166$）。
保证所有测试用例中 $\sum n^2 \le 166^2$。
接下来每组测试用例占一行，包含一个整数 $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})$。
每个三角形顶点输出顺序可以随意（顺时针或逆时针均可）。
只要输出满足所有条件且最大规模正确即可通过。
接下来输出 $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})$。
每个三角形顶点输出顺序可以随意（顺时针或逆时针均可）。
只要输出满足所有条件且最大规模正确即可通过。
输入输出样例
输入 #1
2 1 2
输出 #1
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$ 个三角形，见下左图：
由于三角形不要求为直角三角形，右图中的三角形集合同样是合法的。
在第二个测试用例中，示例输出展示了 $12$ 个三角形，见下左图：
由于三角形不要求为直角三角形，右图中的三角形集合同样是合法的。
