Problem Description

For a three-dimensional convex polyhedron $ P $, its net is defined as a set of polygons on a plane (which may overlap) that satisfy the following conditions:

• Each polygon corresponds one-to-one with a face of $ P $.
• $ P $ can be constructed by repeatedly folding along edges, where folding along an edge means:
• Selecting an edge such that removing it would disconnect the current figure. Rotate the part of the figure on one side of this edge around the axis defined by the edge by any angle (in three dimensions). If necessary, identify vertices or edges that completely coincide in coordinates.

Similarly, the net of the net of a three-dimensional convex polyhedron $ P $ is defined as a set of line segments that satisfy the following conditions:

• Each edge corresponds one-to-one with an edge of the net of $ P $.
• The net of $ P $ can be constructed by repeatedly folding along vertices, where folding along a vertex means:
• Selecting a vertex such that removing it would disconnect the current figure. Rotate the part of the figure on a specific side of this vertex around the vertex by any angle (in two dimensions). If necessary, identify vertices that completely coincide in coordinates.

You are given $ N $ points on the unit sphere, where no four points lie on the same plane. The coordinates of the $ i $-th point are $(x_i, y_i, (-1)^{c_i}\sqrt{1-x_i^2-y_i^2})$.

Determine if there exists a path that is the net of the net of the convex hull of the given points. If it exists, find the maximum length of such a path.

Input Format

The input is given from the standard input in the following format. Real numbers are given up to 6 decimal places.

$ N $ $ x_1 $ $ y_1 $ $ c_1 $ $\vdots$ $ x_N $ $ y_N $ $ c_N $

Output Format

If there exists a path that is the net of the net of the convex hull of the given points, output the answer. Otherwise, output $ -1 $.

The answer is considered correct if the absolute or relative error from the true value is within $ 10^{-7} $.

Sample Input and Output

Sample Input #1

4
0.000000 0.000000 1
0.000000 0.000000 0
1.000000 0.000000 1
0.000000 1.000000 0

Sample Output #1

13.899494936612

Sample Input #2

6
-0.322191 -0.852465 0
-0.463288 -0.553583 1
0.378710 -0.346882 1
-0.489727 0.488028 0
-0.731142 0.227066 1
0.254757 -0.899035 0

Sample Output #2

22.950966056549

Sample Input #3

8
0.837078 0.492956 1
0.360579 -0.565500 0
-0.367448 -0.492394 1
0.491637 -0.658814 1
-0.505114 -0.538563 1
0.544637 0.592884 1
-0.622207 -0.379934 1
0.402129 0.684158 1

Sample Output #3

28.879053537910

Sample Input #4

4
0.800000 0.600000 0
1.000000 0.000000 1
-0.280000 -0.960000 1
0.000000 0.000000 0

Sample Output #4

13.284042973728

Notes/Hints

Constraints

• $4 \leq N \leq 14$
• $-1 \leq x_i, y_i \leq 1$
• $ c_i $ is either $ 0 $ or $ 1 $
• $x_i^2 + y_i^2 \leq 1$
• No two points given are identical
• For any four distinct points $ p, q, r, s $ given, the distance between the plane on which $ p, q, r $ lie and $ s $ is at least $ 10^{-5} $

见题面 Input 部分

见题面 Output 部分