← 返回题目列表

Codeforces · 277/E

E. 平面上的二叉树

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

根树是一种有向无环图,包含一个节点(根),从该节点到任何其他节点只有一条路径。

如果每个节点最多有两个传出弧,则根树是二叉树。

当在平面上绘制二叉树时,所有弧都应从上到下。也就是说,从 u 到 v 的每条弧必须满足条件 yu > yv。

您已获得所有树节点的坐标。你的任务就是用弧连接这些节点,得到二叉根树,并使弧的总长度最小。所构建树的所有弧线必须从上到下。

输入

第一行包含一个整数 n (2 ≤ n ≤ 400) — 树中的节点数。然后跟随 n 行,每行两个整数: xi, yi (|xi|, |yi| ≤ 103) — 节点的坐标。保证所有点都是不同的。

输出

如果无法在给定点上构建二叉根树,则打印“-1”。否则,打印一个实数——最小二叉树中弧的总长度。如果绝对误差或相对误差不超过 10 - 6,则答案将被视为正确。

示例

输入 #1

3
0 0
1 0
2 1

输出 #1

3.650281539872885

输入 #2

4
0 0
1 0
2 1
2 0

输出 #2

-1