e-olymp
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 - 1

Convex hull of the 3D - 1

npoints are given in the space.It is known that no4pointsliein oneplane.Find theconvexhullof these points.

Input

The firstlinecontains thenumberof tests m.The followinglinesdescribetests themselves.Eachtest case startswith a line containingn (1n1000) - the number of points.Further,the nrowsare givenbythree numbers-the points coordinates.Allcoordinatesare integers anddo not exceed500.The totalnumber ofpoints does notexceed22000.

Output

For eachtest case,the output is following.In thefirst line the number of edgesm should be printed. The nextmlines must describe the 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