Minimum triangulation#11259

Minimum triangulation (Editorial)

Consider a triangle that contains the side $(1, n)$ . Let its third vertex be $x$ , then the triangle has the form $(1, n, x)$ (1, n, x).

If $x = n - 1$ x = n - 1, we simply remove the triangle $(1, n, n - 1)$ (1, n, n - 1), after which an $(n - 1)$ (n - 1) - gon remains, which we triangulate further.

If $1 < x < n - 1$ 1 < x < n - 1, consider the triangle $(n, x, k)$ (n, x, k), where $x < k < n$ x < k < n.

Replace the pair of triangles $(1, x, n)$ (1, x, n) and $(n, x, k)$ (n, x, k) with the pair $(1, x, k)$ (1, x, k) and $(1, n, k)$ (1, n, k). The total weight of the triangles decreases, since $x n + x nk > x k + nk$ xn + xnk > xk + nk. After regrouping, we obtain

x (n - k) + nk (x - 1) > 0

x(n - k) + nk(x - 1) > 0

The inequality holds because $n - k > 0$ n - k > 0 and $x - 1 > 0$ x - 1 > 0.

It follows that it is preferable to replace the triangle $(1, x, n)$ (1, x, n) with $(1, k, n)$ (1, k, n), where $k > x$ k > x. Therefore, the optimal choice is $x = n - 1$ x = n - 1. The minimum weight triangulation is obtained by drawing all diagonals from vertex $1$ .

The sum of the weights of all triangles incident to vertex $1$ is equal to

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 + ... + 1 \cdot (n - 1) \cdot n = i = 2 \sum n - 1 i (i + 1)

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 + ... + 1 \cdot (n - 1) \cdot n = \sum_{i = 2}^{n-1} i(i + 1)

Example

In the first test, the polygon is a triangle with vertices $1, 2, 3$ . Its weight is $1 \cdot 2 \cdot 3 = 6$ 1 \cdot 2 \cdot 3 = 6.

In the second test, the polygon is a square with vertices $1, 2, 3, 4$ 1, 2, 3, 4. The minimum weight is achieved by the triangulation with the diagonal $(1, 3)$ :

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18

1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18

Algorithm implementation

Read the input data.

scanf("%d", &n);

Compute the answer.

res = 0;
for (i = 2; i < n; i++)
  res += 1ll * i * (i + 1);

Print the answer.

printf("%lld\n", res);