eolymp
bolt
Try our new interface for solving problems
Try
Problems

Convex hull of the 3D - 1

Convex hull of the 3D - 1

n points are given in the space. It is known that no 4 points lie in one plane. Find the convex hull of these points.

Input

The first line contains the number of tests m. The following lines describe tests themselves. Each test case starts with a line containing n (1 ≤ n ≤ 1000) - the number of points. Further, the n rows are given by three numbers - the points coordinates. All coordinates are integers and do not exceed 500. The total number of points does not exceed 22000.

Output

For each test case, the output is following. In the first line the number of edges m should be printed. The next m lines must describe 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.

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
Show problem classification
Sniper
Direct