分数: 100 点
问题陈述
对于三维凸多面体 P, 净 它的 是满足以下条件的(可能重叠的)多边形的集合。
- 每个多边形与面一一对应 P.
- P 可以通过重复沿其边缘折叠的操作来构造。
这里,沿边折叠是以下操作:
- 选择一条边,删除该边会使当前图形断开连接。使用该边定义的线作为旋转轴,并将位于该边一侧的当前图形的整个部分旋转任意角度(在三个维度中)。如有必要,可识别坐标完全一致的顶点或边。
类似地, 网之网 of 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 is 0 or 1
- x_i^2+y_i^2\leq 1
- 没有两个给定点重合。
- 对于所有四个不同的给定点 p,q,r,s,之间的距离 s 以及其上的平原 p,q,r 存在至少 10^{-5}.
输入
输入由标准输入按以下格式给出:
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