Треугольная головоломка
(Время: 1 сек. Память: 32 Мб Сложность: 60%)
Головоломка состоит из n треугольников. Чтобы решить головоломку, необходимо выбрать из них четыре треугольника и собрать из них большой треугольник по следующей схеме:
Треугольники не должны пересекаться, в объединении они должны давать треугольник. Ровно по одному из выбранных треугольников должны находиться в углах, а один треугольник должен располагаться в центре.
Треугольники лежат на столе, их можно свободно вращать и двигать, но нельзя зеркально отражать.
Требуется найти все различные наборы из четырех треугольников, из которых можно собрать большой треугольник по указанной схеме. Два набора считаются разными, если существует треугольник, входящий в один, но не входящий в другой.
Входные данные
В первой строке входного файла INPUT.TXT записано целое число t – номер теста.
В второй строке дано одно целое число n – количество треугольников в головоломке (4 ≤ n ≤ 30).
В следующих n строках дано описание треугольников. Один треугольник описывается координатами трех своих углов, данных в порядке обхода треугольника против часовой стрелки. Все координаты целые и по модулю не превышают 105. Гарантируется, что треугольники не являются вырожденными. В исходном расположении треугольными могут пересекаться.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите одно целое число – количество наборов из четырех треугольников, из которых можно собрать большой треугольник по указанной схеме.
В следующих строках выведите наборы. Каждый набор задается номерами треугольников, которые в него входят. Треугольники внутри набора можно выводить в любом порядке. Наборы можно выводить в любом порядке.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
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 |
Пояснение
В первом примере из данных четырех треугольников можно собрать один. При этом треугольники не требуется вращать.
Во втором примере все треугольники имеют одинаковую форму прямоугольного треугольника с длинами катетов равными 1. Из любых четырех треугольников можно собрать один.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|