/ 
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
三次元凸多面体 P に対し，その展開図とは，以下を満たす平面上の（重なっても構わない）多角形の集合のことを指します．
- 各多角形は P の面と一対一に対応する
- 辺のいずれかにに沿って折る操作を繰返すことで P を構成することができる．
ただし，辺に沿って折るとは以下の操作です．
- 辺であって，その辺を取り除くと現在の図形が非連結になるものを取る．その辺で定義される直線を中心軸として，現在の図形上でその辺の片側に位置する部分全体を，任意の角度だけ（三次元的に）回転させる．必要なら，座標の完全に一致した頂点や辺を同一視する．
同様に，三次元凸多面体 P の展開図の展開図とは，以下を満たす線分の集合のことを指します．
- 各辺は P の展開図の辺と一対一に対応する
- 頂点に沿って折ることを繰返すことで，P の展開図を構成することができる．
ただし，頂点に沿って折るとは以下の操作です．
- 頂点であって，その頂点を取り除くと現在の図形が非連結になるものを取る．その頂点を中心に，現在の図形上でその頂点の特定の側に位置する部分全体を，任意の角度だけ（二次元的に）回転させる．必要なら，座標の完全に一致した頂点を同一視する．
どの四頂点も同一平面上にない，単位球面上の N 点が与えられます． i 番目の点の座標は (x_i,y_i,(-1)^{c_i}\sqrt{1-x_i^2-y_i^2}) です．
与えられた点たちの凸包の展開図の展開図であって，パスであるものが存在するか判定してください． 存在する場合は，そのパスの長さの最大値を求めてください．
制約
- 4 \leq N \leq 14
- -1\leq x_i,y_i\leq 1
- c_i は 0 または 1
- x_i^2+y_i^2\leq 1
- 与えられるどの 2 点も相異なる
- 与えられるすべての異なる四点 p,q,r,s に対して，p,q,r が乗っている平面と s の間の距離は 10^{-5} 以上
入力
入力は以下の形式で標準入力から与えられる．実数は小数点以下 6 桁まで与えられる．
N x_1 y_1 c_1 \vdots x_N y_N c_N
出力
与えられた点たちの凸包の展開図の展開図であってパスであるものが存在するなら，答えを出力せよ． そうでない場合，-1 を出力せよ．
真の値との絶対誤差あるいは相対誤差が 10^{-7} 以下の場合に正答とみなされる．
入力例 1
4 0.000000 0.000000 1 0.000000 0.000000 0 1.000000 0.000000 1 0.000000 1.000000 0
出力例 1
13.899494936612
たとえば，図のような展開が最適です．
図: 展開の例
入力例 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
出力例 2
22.950966056549
入力例 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
出力例 3
28.879053537910
入力例 4
4 0.800000 0.600000 0 1.000000 0.000000 1 -0.280000 -0.960000 1 0.000000 0.000000 0
出力例 4
13.284042973728
Score : 100 points
Problem Statement
For a three-dimensional convex polytope P, the net of it is the set of (possibly overlapping) polygons satisfying the following.
- Each polygon corresponds one-to-one with a face of P.
- P can be constructed by repeating the operation of folding along its edges.
Here, folding along an edge is the following operation:
- Choose an edge, the removal of which would make the current figure disconnected. Use the line defined by this edge as the axis of rotation and rotate the entire part of the current figure that lies on one side of this edge by any angle (in three dimensions). If necessary, vertices or edges that coincide exactly in coordinates are identified.
Similarly, the net of the net of P is the set of line segments satisfying the following.
- Each edge corresponds one-to one with an edge of the net of P.
- The net of P can be constructed by repeating the operation of folding along its vertices.
Here, folding along a vertex is the following operation:
- Choose a vertex, the removal of which would make the current figure disconnected. Use this vertex as the center of rotation and rotate the entire part of the current figure that lies on some side of this vertex by any angle (in two dimentions). If necessary, vertices that coincide exactly in coordinates are identified.
You are given N points on the unit sphere such that no four of these are on the same plain. The coordinate of i-th point is given by (x_i,y_i,(-1)^{c_i}\sqrt{1-x_i^2-y_i^2}).
Determine whether there exists a net of a net of the convex hull of given points, which is a path. If exists, compute the largest length of such path.
Constraints
- 4 \leq N \leq 14
- -1\leq x_i,y_i\leq 1
- c_i is 0 or 1
- x_i^2+y_i^2\leq 1
- No two given points coincide.
- For all four different given points p,q,r,s, the distance between s and the plain on which p,q,r exist is at least 10^{-5}.
Input
The input is given from Standard Input in the following format:
N x_1 y_1 c_1 \vdots x_N y_N c_N
Output
If there exists a net of a net of the convex hull of given points, which is a path, print the largest possible length.
If not print -1.
An output is considered correct if the absolute or the relative error from the true value is at most 10^{-7}.
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
The following net of net is optimal.
Figure: the optimal net of the net.
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