SP7211 ELASTIC - Elastic Bands

圆周连接研究所（ICPC）最近发现，多个生产区域的机器已经严重过时。显然，这些机器都包含多个圆形部件。ICPC 的最高主管委托他们的计算机辅助问题解决部门来帮助解决这一问题，而你正是被指定的负责人，所以请马上行动起来。 研究所中的很多机器都需要通过旋转顺时针方向的圆形机械部件来运作。目前，每个圆形部件都连接到单独的电动机。然而你注意到，当多个圆共面时，可以使用橡皮筋将它们连接在一起，这样只需一个电动机便可使它们同时旋转。 这个绝妙的主意引出了一个新问题：如何最优地连接所有的圆？一般来说，有很多种方法可以安排橡皮筋，使所有的圆连接在一起。由于部分旋转能量会被橡皮筋的张力消耗，你希望尽可能地减少橡皮筋的总长度。 具体来说，连接两个圆的橡皮筋的长度是包含这两个圆的最小凸包的周长。总长度是所有所用橡皮筋的长度之和。即便橡皮筋接触或穿过其它圆或橡皮筋，也可以进行连接。

输入包含多个测试用例，每个测试用例由多行构成。第一行是一个整数 $N$，表示需要连接的圆的数量（$2 \le N \le 2000$）。接下来的 $N$ 行中，每行分别使用三个整数 $X, Y, R$ 表示一个圆（$-10^4 \le X, Y \le 10^4$，$1 \le R \le 1000$），其中 $X$ 和 $Y$ 是圆心的坐标，$R$ 是半径。在每个测试用例中，所有圆互不重叠或相接。输入的最后一行是一个单独的 $-1$，这行不作为测试用例处理。

每个测试用例输出一行，包含一个实数，表示连接所有圆所需橡皮筋的最小总长度。结果保留到小数点后三位，并使用四舍五入规则。如果遇到平局，则向上取整。无论如何，最后的结果必须包含三位小数，即使这意味着在数字后添加零。

$$2 \le N \le 2000$$ $$-10^4 \le X, Y \le 10^4$$ $$1 \le R \le 1000$$ **本翻译由 AI 自动生成**