Processing math: 100%

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

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

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

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

Формат входных данных

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

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

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

Формат выходных данных

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

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

Ограничения

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

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

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

Тест Описание теста
1тест из примера, не оценивается
2тест из примера, не оценивается
3Все треугольники равны с точностью до поворота, n30
4У каждого треугольника есть горизонтальная и вертикальная стороны, все треугольники равнобедренные, n10
5У каждого треугольника есть горизонтальная и вертикальная стороны, все треугольники равнобедренные, n30
6У каждого треугольника есть горизонтальная и вертикальная стороны, n10
7У каждого треугольника есть горизонтальная и вертикальная стороны, n30
8Все треугольники прямоугольные, n10
9Все треугольники прямоугольные, n30
10Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, n10
11Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, n20
12Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, n30
13n=10
14n=10
15n=10
16n=20
17n=20
18n=20
19n=30
20n=30
21n=30
22n=30

Пояснение к примеру

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

Во втором примере все треугольники имеют одинаковую форму прямоугольного треугольника с длинами катетов равными 1. Из любых четырех треугольников можно собрать один.

Примеры тестов

Стандартный вход Стандартный выход
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
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 

0.071s 0.008s 15