Задача №115200. Треугольная головоломка

Головоломка состоит из $n$ треугольников. Чтобы решить головоломку, необходимо выбрать из них четыре треугольника и собрать из них большой треугольник по следующей схеме:

$\text{[math]}$

Треугольники не должны пересекаться, в объединении они должны давать треугольник. Ровно по одному из выбранных треугольников должны находиться в углах, а один треугольник должен располагаться в центре.

Треугольники лежат на столе, их можно свободно вращать и двигать, но нельзя зеркально отражать.

Требуется найти все различные наборы из четырех треугольников, из которых можно собрать большой треугольник по указанной схеме. Два набора считаются разными, если существует треугольник, входящий в один, но не входящий в другой.

Входные данные

В первой строке дано одно целое число $t$ — номер теста.

В второй строке дано одно целое число $n$ — количество треугольников в головоломке ($4 \le n \le 30$).

В следующих $n$ строках дано описание треугольников. Один треугольник описывается координатами трех своих углов, данных в порядке обхода треугольника против часовой стрелки. Все координаты целые и по модулю не превышают $10^5$. Гарантируется, что треугольники не являются вырожденными. В исходном расположении треугольники могут пересекаться.

Выходные данные

В первой строке выведите одно целое число — количество наборов из четырех треугольников, из которых можно собрать большой треугольник по указанной схеме.

В следующих строках выведите наборы. Каждый набор задается номерами треугольников, которые в него входят. Треугольники внутри набора можно выводить в любом порядке. Наборы можно выводить в любом порядке.

Система оценки

В этой задаче потестовая оценка. Каждый тест оценивается независимо и стоит $5$ баллов.

Тесты удовлетворяют следующим ограничениям:

Тест	Описание теста
1	тест из примера, не оценивается
2	тест из примера, не оценивается
3	Все треугольники равны с точностью до поворота, $n \le 30$
4	У каждого треугольника есть горизонтальная и вертикальная стороны, все треугольники равнобедренные, $n \le 10$
5	У каждого треугольника есть горизонтальная и вертикальная стороны, все треугольники равнобедренные, $n \le 30$
6	У каждого треугольника есть горизонтальная и вертикальная стороны, $n \le 10$
7	У каждого треугольника есть горизонтальная и вертикальная стороны, $n \le 30$
8	Все треугольники прямоугольные, $n \le 10$
9	Все треугольники прямоугольные, $n \le 30$
10	Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, $n \le 10$
11	Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, $n \le 20$
12	Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, $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$

Примечание

В первом примере из данных четырех треугольников можно собрать один. При этом треугольники не требуется вращать.

Во втором примере все треугольники имеют одинаковую форму прямоугольного треугольника с длинами катетов равными $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

Выходные данные

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

Выходные данные

Сдать: для сдачи задач необходимо войти в систему

Тест	Описание теста
1	тест из примера, не оценивается
2	тест из примера, не оценивается
3	Все треугольники равны с точностью до поворота, \(n \le 30\)
4	У каждого треугольника есть горизонтальная и вертикальная стороны, все треугольники равнобедренные, \(n \le 10\)
5	У каждого треугольника есть горизонтальная и вертикальная стороны, все треугольники равнобедренные, \(n \le 30\)
6	У каждого треугольника есть горизонтальная и вертикальная стороны, \(n \le 10\)
7	У каждого треугольника есть горизонтальная и вертикальная стороны, \(n \le 30\)
8	Все треугольники прямоугольные, \(n \le 10\)
9	Все треугольники прямоугольные, \(n \le 30\)
10	Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, \(n \le 10\)
11	Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, \(n \le 20\)
12	Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, \(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\)