题目描述
Problem Background
Translated from ROIR 2022 D1T3.
A puzzle consists of $n$ triangles. To successfully solve the puzzle, you need to select four triangles and combine them into one large triangle according to the following rules:
These triangles must not intersect, and their combination must form a triangle. Exactly three of the selected four triangles are located at the corners, and one triangle is located at 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 different 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 not to another, the two sets are considered different.
Input Format
The first line contains an integer $t$, representing the current test point number.
The second line contains an integer $n$, representing the number of triangles in the puzzle ($4 \le n \le 30$).
The next $n$ lines each contain six numbers, representing the coordinates of the three vertices of a triangle in counterclockwise order. All coordinates are integers and do not exceed $10^5$. It is guaranteed that the triangles will not degenerate into straight lines. The initial positions of the triangles may intersect.
Output Format
The first line outputs an integer, representing the number of sets of four triangles that can be combined into a large triangle according to the specified rules.
The following lines output these sets. Each set consists of the numbers of the triangles it contains. The triangles within a set can be output in any order. The order of the sets is also arbitrary.
Sample Input and Output
Sample Input #1
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
Sample Output #1
1
1 2 3 4
Sample Input #2
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
Sample Output #2
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
Notes
This problem consists of 22 test points. The first two test points are examples and passing them does not award points. Each of the remaining 20 test points is worth 5 points.
| Test Point Number | Special Properties |
|---|---|
| 1 | Input data is example 1 |
| 2 | Input data is example 2 |
| 3 | All triangles are congruent, $n \le 30$ |
| 4 | All triangles have one horizontal and one vertical side and are isosceles, $n \le 10$ |
| 5 | All triangles have one horizontal and one vertical side and are isosceles, $n \le 30$ |
| 6 | All triangles have one horizontal and one vertical side, $n \le 10$ |
| 7 | All triangles have one horizontal and one vertical side, $n \le 30$ |
| 8 | All triangles are right triangles, $n \le 10$ |
| 9 | All triangles are right triangles, $n \le 30$ |
| 10 | All four triangles that can form a large triangle do not require rotation, $n \le 10$ |
| 11 | All four triangles that can form a large triangle do not require rotation, $n \le 20$ |
| 12 | All four triangles that can form a large triangle do not require rotation, $n \le 30$ |
| 13 | $n = 10$ |
| 14 | $n = 10$ |
| 15 | $n = 10$ |
| 16 | $n = 20$ |
| 17 | $n = 20$ |
| 18 | $n = 20$ |
| 19 | $n = 30$ |
| 20 | $n = 30$ |
| 21 | $n = 30$ |
| 22 | $n = 30$ |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分