P15724 [JAG 2023 Summer Camp #3] Convex Polygon MST

平面上有一个具有 $n$ 个顶点的凸多边形。令 $V$ 为该凸多边形的顶点集合。在移除凸多边形的所有边之后，你将通过重复以下操作 $n - 1$ 次来构造一棵包含 $n$ 个顶点的树： - 选择两个不同的顶点 $x, y \in V$。在顶点 $x$ 和 $y$ 之间添加一条边。若记顶点 $x$ 和 $y$ 之间的欧几里得距离为 $d(x, y)$，你将获得 $(d(x, y))^2$ 分。 求通过 $n - 1$ 次操作所能获得的最大总分数。

输入文件包含多个测试用例。第一行包含一个整数 $t$，表示测试用例的数量。随后给出 $t$ 个测试用例。每个测试用例的格式如下： $$ \begin{aligned} &n \\ &x_1 \ y_1 \\ &\vdots \\ &x_n \ y_n \end{aligned} $$ 其中，$n$ 是一个表示顶点数量的整数，满足 $3 \leq n \leq 120,000$。单个输入文件中所有 $n$ 值的总和保证不超过 $120,000$。 $x_i$ 和 $y_i$ 表示第 $i$ 个顶点的坐标，每个坐标是介于 $-10^9$ 到 $10^9$ 之间的整数。顶点按从凸多边形质心观察的逆时针顺序给出。凸多边形的任意三个不同顶点不共线。

输出通过 $n - 1$ 次操作所能获得的最大总分数。

- 坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的欧几里得距离计算公式为 $\sqrt{|x_1 - x_2|^2 + |y_1 - y_2|^2}$。 - 请注意，答案可能超过 $2^{64}$。 翻译由 DeepSeek V3.2 完成