Convex hull of the 3D - 2
Convex hull of the 3D - 2
n
points are given in the space. No 4 points lie in one plane. Find the convex hull of these points.
Input
The first line contains the number of test cases m
. The following lines describe the tests. Each test starts with a line containing n
(1 ≤ n ≤ 1000
) - number of points. Further, the n rows are given by three numbers - the coordinates of points. All coordinates are integers, do not exceed 500. The total number of points does not exceed 2100.
Output
For each test, the following output. In the first line of the output number of edges m
. Coming up next m
lines output description of the faces: the number of vertices and number of points in the original set. The points are numbered in the order in which they are given in the input file. Points within the faces must be sorted in order of counterclockwise relative to the outer normal to the face.
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 ...
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 ...