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 - 3

Convex hull of the 3D - 3

Givennpointsin space.No4pointsdo not liein oneplane.Find theconvexhullof these points.

Input

The firstlinecontains thenumbern (4n100).Further,the nrowsare givenbythree numbers-the coordinatesof points.Allcoordinatesare integers,do not exceed500.

Output

In thefirst line of theoutputnumber of edgesm.Coming upnextm linesoutputdescription 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 2 seconds
Memory limit 256 MiB
Input example #1
4
0 0 0
1 0 0
0 1 0
0 0 1
Output example #1
4
3 0 1 3
3 0 2 1
3 0 3 2
3 1 2 3
Author Stanislav Pak
Source Winter School, Kharkov, 2011, Day 1