2195H. Codeforces Heuristic Contest 001（Enhanced)

Brute force, constructive algorithms, georgetry, implementation

https://codeforces.com/problemset/problem/2195/H

There is a grid of 3𝑛×3𝑛 points, consisting of all integer points (𝑥,𝑦) such that 1≤𝑥,𝑦≤3𝑛.

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 12. 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.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤30). The description of the test cases follows.

The only line of each test case contains a single integer 𝑛 (1≤𝑛≤166).

It is guaranteed that the sum of 𝑛2 over all test cases does not exceed 1662.

Output

Output the maximum size 𝑚 of the set of triangles on one line (0≤𝑚≤3𝑛2).

Then, output 𝑚 lines in the following format:

𝑥𝑖,1𝑦𝑖,1𝑥𝑖,2𝑦𝑖,2𝑥𝑖,3𝑦𝑖,3: The vertices of the 𝑖-th triangle are (𝑥𝑖,1,𝑦𝑖,1), (𝑥𝑖,2,𝑦𝑖,2), (𝑥𝑖,3,𝑦𝑖,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.

Example

input

Copy

2
1
2

output

Copy

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

Note

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.

【尹显齐 2500011456 物理学院】

（在加强版中，你只能使用三边长度分别为 $1, 1, \sqrt{2}$ 的三角形）

本关考验你的连线能力！ 首先，我们要明确答案。当 $n = 1$ 时，明显只能放下两个三角形。当 $n$ 为偶数时，明显能通过不断在 $3 \times 2$ 的点阵里放两个三角形占据所有点。问题就是当 $n$ 是除了 $1$ 以外的奇数时，能否放满。容易看出，如果我们能将一个 $x \times 3 y$ （均为奇数）的点阵用三角形占满，就能利用 $3 \times 2$ 的点阵里能放两个三角形占据所有点的性质先扩展成 $(x + 2 a) \times 3 y$ 的点阵，再扩展成 $(x + 2 a) \times 3 (y + b)$ 的点阵，从而满足题目要求。所以关键就是寻找能将一个 $x \times 3 y$ （均为奇数）的点阵用三角形占满的方法。显然，我们发现 $y$ 的最小值为 $3$ ，于是我们可以一个一个试 $x$ （推荐用几何画板，能自动吸附格点），在 $x = 5$ 时，有如下方法： ![[Pasted image 20260305230104.png|center|600]] 故问题得以解决。

代码：（仅供参考，且与上图不对应）

python

ans = [[1,1,1,2,2,1],[3,1,2,2,3,2],[4,1,4,2,5,1],[5,2,6,1,7,1],[7,2,8,1,9,1],[1,3,2,3,1,4],[3,3,3,4,4,3],[5,3,6,2,5,4],[6,3,7,3,7,4],[8,2,9,2,9,3],[1,5,2,4,2,5],[3,5,4,4,4,5],[5,5,6,4,6,5],[7,5,8,4,8,5],[8,3,9,4,9,5]]
for _ in range(int(input())):
    n = int(input())
    if n == 1:
        print(2)
        print("1 1 1 2 2 1")
        print("2 3 3 2 3 3")
    elif n % 2 == 0:
        print(3*n**2)
        for i in range(n):
            for j in range(3*n//2):
                s = (3*i,2*j)
                print(f"{s[0]+1} {s[1]+1} {s[0]+1} {s[1]+2} {s[0]+2} {s[1]+1}")
                print(f"{s[0]+2} {s[1]+2} {s[0]+3} {s[1]+1} {s[0]+3} {s[1]+2}")
    else:
        print(3*n**2)
        for i in range(15):
            print(*ans[i])
        for i in range((3*n-9)//2):
            for j in range(n):
                s = (2*i+9,3*j)
                print(f"{s[0]+1} {s[1]+1} {s[0]+1} {s[1]+2} {s[0]+2} {s[1]+1}")
                print(f"{s[0]+2} {s[1]+2} {s[0]+1} {s[1]+3} {s[0]+2} {s[1]+3}")
        for i in range(3):
            for j in range((3*n-5)//2):
                s = (3*i,2*j+5)
                print(f"{s[0]+1} {s[1]+1} {s[0]+1} {s[1]+2} {s[0]+2} {s[1]+1}")
                print(f"{s[0]+2} {s[1]+2} {s[0]+3} {s[1]+1} {s[0]+3} {s[1]+2}")

2195H. Codeforces Heuristic Contest 001（Enhanced) ​

2195H. Codeforces Heuristic Contest 001（Enhanced)