favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

# Convex hull of the 3D - 2

npoints are given in the space.No4pointsliein oneplane.Find theconvexhullof these points.

Input

The firstlinecontains thenumberof test cases m.The followinglinesdescribethe tests.Eachteststartswith a line containingn (1n1000) -number of points.Further,the nrowsare givenbythree numbers-the coordinatesof points.Allcoordinatesare integers,do not exceed500.The totalnumber ofpoints does notexceed2100.

Output

For eachtest,the followingoutput.In thefirst line of theoutputnumber of edgesm.Coming upnextm lines outputdescription ofthe faces:the numberof verticesandnumberof pointsin the originalset.The pointsare numberedin theorderinwhichthey aregivenin the inputfile. Pointswithin thefaces mustbesortedin order ofcounterclockwiserelative to the outernormalto theface.

Time limit 1 second
Memory limit 256 MiB
Input example #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
...
Output example #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
...
Author Stanislav Pak
Source Winter School, Kharkov, 2011, Day 1