A16715 | $Codeforces Heuristic Contest 001$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个 $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})$。 每个三角形顶点输出顺序可以随意（顺时针或逆时针均可）。 只要输出满足所有条件且最大规模正确即可通过。

输入输出样例

输入 #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

C++ 编辑器

输入

输出

A16715 | Codeforces Heuristic Contest 001

题目描述

输入格式

输出格式

输入输出样例

A16715 | $Codeforces Heuristic Contest 001$