Background

Translated from ROIR 2022 D1T3.

There is a puzzle consisting of $n$ triangles. To solve this puzzle, you need to choose four triangles and combine them into one large triangle according to the following rules:

These triangles must not intersect, and their union must form a triangle. Among the four chosen triangles, exactly three triangles are at the corners, and the remaining one triangle is in the center.

The triangles are placed on a table and can be freely rotated and moved, but cannot be flipped.

Problem Description

You need to find all sets of four distinct triangles that can be combined into a large triangle according to the specified rules. If there exists a triangle that belongs to one set but does not belong to another set, then the two sets are considered different.

Input Format

The first line contains an integer $t$, the index of the current test point.

The second line contains an integer $n$, the number of triangles in the puzzle ($4 \le n \le 30$).

The next $n$ lines each contain six numbers, describing the coordinates of the three vertices of a triangle, given in counterclockwise order. All coordinates are integers and do not exceed $10^5$. It is guaranteed that no triangle degenerates into a line segment. Triangles in the initial positions may intersect.

Output Format

The first line outputs an integer, the number of sets of four triangles that can be combined into a large triangle according to the specified rules.

Each of the following lines outputs one such set. Each set is given by the indices of the triangles it contains. The triangles within a set may be output in any order. The sets themselves may also be output in any order.

1
4
0 0 6 2 1 2
0 0 5 0 6 3
0 0 3 1 1 3
0 0 6 3 3 6

1
1 2 3 4

2
6
0 0 1 0 1 1
0 1 0 0 1 0
-1 0 0 0 0 1
1 1 0 1 1 0
-1 0 0 -1 0 0
0 0 1 1 0 1

15
1 2 3 4
1 2 3 5
1 2 3 6
1 2 4 5
1 2 4 6
1 2 5 6
1 3 4 5
1 3 4 6
1 3 5 6
1 4 5 6
2 3 4 5
2 3 4 6
2 3 5 6
2 4 5 6
3 4 5 6

Hint

This problem has $22$ test points. The first two test points are samples; passing them gives no score. The remaining $20$ test points are worth $5$ points each.

Translated by ChatGPT 5