题目描述

There is a convex polygon with $n$ vertices on a plane. Let $V$ be the set of vertices of this convex polygon. After removing all the edges of the convex polygon, you will create a tree with $n$ vertices by repeating the following operation $n - 1$ times:

• Select two distinct vertices $x, y \in V$. Add an edge between vertices $x$ and $y$. If we denote the Euclidean distance between vertices $x$ and $y$ as $d(x, y)$, you gain a score of $(d(x, y))^2$ points.

Find the maximum possible total score obtained by $n - 1$ operations.

输入格式

The input file contains multiple test cases. The first line contains an integer $t$ representing the number of test cases. Following that, $t$ test cases are given. Each test case is given in the following format:

$$\begin{aligned} &n \\ &x_1 \ y_1 \\ &\vdots \\ &x_n \ y_n \end{aligned} $$

Here, $n$ is an integer representing the number of vertices, where $3 \leq n \leq 120,000$. The sum of all $n$ values in a single input file is guaranteed to be less than or equal to $120,000$.

$x_i$ and $y_i$ represent the coordinates of the $i$-th vertex, where each coordinate is an integer between $-10^9$ to $10^9$. The vertices are given in counterclockwise order when viewed from the centroid of the convex polygon. Three different vertices of the convex polygon do not lie on a single line.

输出格式

Output the maximum possible total score obtained by $n - 1$ operations.

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

提示

• The Euclidean distance between coordinates $(x_1, y_1)$ and $(x_2, y_2)$ is calculated as $\sqrt{|x_1 - x_2|^2 + |y_1 - y_2|^2}$.
• Note that the answer can exceed $2^{64}$.