← 返回题目列表

AtCoder · 1202Contest_g

G. 网之网

中文机器翻译题面 查看原题

分数: 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