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

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.

- 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}$.