24877번 - Треугольная головоломка 점수다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 5 | 1 | 1 | 25.000% |
문제
Головоломка состоит из $n$ треугольников. Чтобы решить головоломку, необходимо выбрать из них четыре треугольника и собрать из них большой треугольник по следующей схеме:
Треугольники не должны пересекаться, в объединении они должны давать треугольник. Ровно по одному из выбранных треугольников должны находиться в углах, а один треугольник должен располагаться в центре.
Треугольники лежат на столе, их можно свободно вращать и двигать, но нельзя зеркально отражать.
Требуется найти все различные наборы из четырех треугольников, из которых можно собрать большой треугольник по указанной схеме. Два набора считаются разными, если существует треугольник, входящий в один, но не входящий в другой.
입력
В первой строке дано одно целое число $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 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
예제 출력 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
힌트
В первом примере из данных четырех треугольников можно собрать один. При этом треугольники не требуется вращать.
Во втором примере все треугольники имеют одинаковую форму прямоугольного треугольника с длинами катетов равными $1$. Из любых четырех треугольников можно собрать один.
출처
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2022 3번
채점 및 기타 정보
- 110점 이상을 획득해야 를 받는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호