CF277E Binary Tree on Plane

一棵有根树是一个有向无环图，它有一个根节点，从根可以出发到达任意其它节点并且每个节点恰好有一条从根到该节点的路径。 一棵二叉树是指树中每个节点最多只有两条出边。 当二叉树被“画”在平面上时，要求所有的边都由上往下连接。即，任意一条由 $u$ 到 $v$ 的有向边，都需要满足 $y_u > y_v$。 你得到了所有树中节点的坐标。你的任务是将这些节点用有向边连接起来，使其构成一棵有根二叉树，并且使得所有树边的总长度最小。所有树中的边都必须由上向下。

第一行包含一个整数 $n$（$2 \leq n \leq 400$）——树中节点数。接下来 $n$ 行，每行两个整数 $x_i, y_i$（$|x_i|,|y_i| \leq 10^3$）——节点的坐标。保证所有点两两不同。

如果无法用这些点构造一棵有根二叉树，输出 “-1”。否则，输出一个实数，表示最小总长度的二叉树中所有边的总长度。你的答案如果与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 都将被判为正确。

由 ChatGPT 5 翻译