AT_1202Contest_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_i2\leq\ 1 $
• 给出的任意两个点都不同
• 给出的所有不同的四个点$p,q,r,s$，$p,q,r$所在的平面与$s$之间的距离大于$10^{-5}$

Translate by @XYQ_102