AT1202Contest_g Net of Net

给定一个三维凸多面体 $P$，它的展开图是指满足以下条件的平面上的多边形集合： - 每个多边形与 $P$ 的一个面一一对应 - 通过沿着边进行折叠操作，可以构造出 $P$ 其中，沿着边进行折叠的操作定义如下： - 选择一条边，使得如果移除该边，当前的图形将变为非连通的。然后，以该边为轴，在当前图形上，将该边的一侧部分整体旋转任意角度（在三维空间中）。如果需要，可以将完全相同的顶点或边等同视之。 类似地，三维凸多面体 $P$ 的展开图的展开图是指满足以下条件的线段集合： - 每条边与 $P$ 的展开图的边一一对应 - 通过沿着顶点进行折叠操作，可以构造出 $P$ 的展开图 其中，沿着顶点进行折叠的操作定义如下： - 选择一个顶点，使得如果移除该顶点，当前的图形将变为非连通的。然后，以该顶点为中心，在当前图形上，将该顶点的特定侧部分整体旋转任意角度（在二维空间中）。如果需要，可以将完全相同的顶点等同视之。 给定一组在单位球面上的 $N$ 个点，其中任意四个点都不在同一平面上。点 $i$ 的坐标为$(x_i,y_i,(-1)^{c_i}\sqrt{1-x_i^2-y_i^2})$。 判断是否存在点集的凸包的展开图的展开图是一条路径，并计算该路径的最大长度。

输入以以下形式从标准输入中给出。实数的小数部分最多包含6位。 > $ N $ $ x_1 $ $ y_1 $ $ c_1 $ $ \vdots $ $ x_N $ $ y_N $ $ c_N $

如果存在点集的凸包的展开图的展开图是一条路径，则输出答案。否则，输出-1。 真实答案与你的答案的绝对误差或相对误差不超过$10^{-7}$时，才被认为是正确的。 ### 约束条件 - $ 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 $ - 给出的任意两个点都不同 - 给出的所有不同的四个点$p,q,r,s$，$p,q,r$所在的平面与$s$之间的距离大于$10^{-5}$ Translate by [@XYQ_102](https://www.luogu.com.cn/user/712337)

### 制約 - $ 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} $ 以上 ### Sample Explanation 1 たとえば，図のような展開が最適です． !\[\](https://img.atcoder.jp/DEGwer2023/G\_zu.png)図: 展開の例