avatarГость
← К соревнованиям

Всероссийская олимпиада школьников (Региональный этап)

Треугольная головоломка

Сложность: 52%

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

image

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подзадачи

№баллынеобх. подзадачиограничения
0

0

-

Тесты из условия

1

100

-

См. систему оценки

STDINSTDOUT
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

Примечание

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

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