说明

平面上有一个具有 $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$ 次操作所能获得的最大总分数。

2
4
0 0
1 0
1 1
0 1
6
986288255 165031740
-353860917 -935298054
-173584601 -984818960
141060317 -990001002
341839727 -939758266
662792114 -748803453

5
10426936519662708146

提示

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

翻译由 DeepSeek V3.2 完成