Задачі
Опукла оболонка 3D - 1
Опукла оболонка 3D - 1
Задано \textbf{n} точок у просторі. Ніякі \textbf{4} точки не лежать в одній площині. Знайдіть опуклу оболочку цих точок.
\textbf{Вхідні данні}
Перший рядок містить число \textbf{m} --- кількість тестів. У наступних рядках описані самі тести. Кожен тест починається з рядка, що містить \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000}) --- число точок. Далі, в \textbf{n} рядках задано по три числа --- координати точок. Всі координати цілі, не перевищують по модулю \textbf{500}. Загальна кількість точок не перевищує \textbf{22000}.
\textbf{Вихідні данні}
Для кожного тесту виведіть наступне. У першому рядку виведіть кількість граней \textbf{m}. Далі у наступних \textbf{m} рядках виведіть описи граней: кількість вершин та номери точок у заданій множині. Точки нумеруються у тому ж порядке, у якому вони задані у вхідному файлі. Точки в мажах грані повинні бути відсортовані у порядку проти годинникової стрілки відносно зовнішньої нормалі до грані.
Вхідні дані #1
50 4 0 0 0 1 0 0 0 1 0 0 0 1 4 0 0 0 10 0 0 0 10 0 10 10 10 5 0 0 0 10 0 0 0 10 0 10 10 10 5 5 1 5 0 0 0 10 0 0 0 10 0 10 10 10 5 5 10 8 340 -107 -403 -317 -231 465 475 -451 96 -199 31 -438 374 431 -365 194 181 342 -167 336 -195 -400 -435 -103 12 349 71 456 -81 -189 -339 220 432 228 43 221 158 -307 53 -205 6 380 -146 195 -19 -210 -64 321 -365 92 140 30 -201 131 166 239 99 -130 124 14 -125 17 359 248 315 155 -147 169 -34 314 360 286 -280 -248 12 -325 -45 128 269 -324 247 317 85 -418 77 -317 17 393 -439 323 442 -391 -314 -331 -127 135 164 -106 439 -276 -19 257 472 -300 287 -254 486 -285 216 -204 421 296 312 7 -322 -265 -137 391 -106 -324 -288 197 492 -162 -90 -343 22 297 -195 -60 468 189 -393 -37 71 12 -312 -87 -279 -64 -64 -127 459 79 -377 80 100 253 342 -81 -35 61 358 -299 -341 -392 56 256 -412 159 -444 -412 316 -323 374 498 272 -189 260 -152 -226 -377 15 100 280 -24 -89 -370 219 -480 -280 -154 -160 204 -250 -194 306 37 -15 105 432 276 -76 -129 -83 169 -154 -430 371 116 203 -438 28 23 ...
Вихідні дані #1
4 3 0 1 3 3 0 2 1 3 0 3 2 3 1 2 3 4 3 0 1 3 3 0 2 1 3 0 3 2 3 1 2 3 4 3 0 1 3 3 0 2 1 3 0 3 2 3 1 2 3 6 3 0 1 4 3 0 2 1 3 0 4 2 3 1 2 3 3 1 3 4 3 2 4 3 12 3 0 2 7 3 0 3 4 3 0 4 2 3 0 7 3 3 1 2 5 3 1 5 6 3 1 6 7 3 1 7 2 3 2 4 5 3 3 6 4 3 3 7 6 3 4 6 5 14 3 0 1 6 3 0 2 9 3 0 6 10 3 0 9 1 3 0 10 2 3 1 4 7 3 1 7 6 3 1 9 4 3 2 5 9 3 2 7 5 3 2 10 7 3 4 5 7 3 4 9 5 3 6 7 10 20 3 2 7 10 3 2 8 15 3 2 10 14 3 2 13 8 3 2 14 16 3 2 15 7 3 2 16 13 3 3 4 10 3 3 7 8 3 3 8 9 3 3 9 12 3 3 10 7 3 3 12 4 3 4 12 14 3 4 14 10 3 7 15 8 3 8 13 9 3 9 13 16 3 9 16 12 3 12 16 14 10 3 0 1 2 3 0 2 6 3 0 3 1 3 0 6 3 3 1 3 4 3 1 4 5 3 1 5 2 3 2 5 6 3 3 6 4 3 4 6 5 16 3 0 5 11 3 0 6 8 3 0 8 9 3 0 9 5 3 0 11 6 3 2 3 10 3 2 5 9 3 2 7 11 3 2 9 3 3 2 10 7 3 2 11 5 3 3 9 10 3 6 7 8 3 6 11 7 3 7 10 8 3 8 10 9 18 3 0 3 12 3 0 10 13 3 0 12 10 3 0 13 3 3 1 2 9 3 1 9 11 3 1 11 12 3 1 12 2 3 2 3 13 3 2 8 3 3 2 12 8 3 2 13 9 3 3 8 12 3 5 10 12 3 5 11 10 3 5 12 11 3 9 13 11 3 10 11 13 6 3 0 1 4 3 0 2 5 3 0 4 2 3 0 5 1 3 1 2 4 3 ...