CF2195H Codeforces Heuristic Contest 001

There is a grid of $ 3n \times 3n $ points, consisting of all integer points $ (x,y) $ such that $ 1 \le x,y \le 3n $ . 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 $ \frac{1}{2} $ . 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.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 30 $ ). The description of the test cases follows. The only line of each test case contains a single integer $ n $ ( $ 1 \le n \le 166 $ ). It is guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 166^2 $ .

Output the maximum size $ m $ of the set of triangles on one line ( $ 0 \le m \le 3n^2 $ ). Then, output $ m $ lines in the following format: - $ x_{i,1}\;y_{i,1}\;x_{i,2}\;y_{i,2}\;x_{i,3}\;y_{i,3} $ : The vertices of the $ i $ -th triangle are $ (x_{i,1},y_{i,1}) $ , $ (x_{i,2},y_{i,2}) $ , $ (x_{i,3},y_{i,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.

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.