Мінімальна тріангуляція

Вам задано правильний багатокутник з $n$ вершинами, пронумерованими від $1$ до $n$ проти годинникової стрілки.

Тріангуляція даного багатокутника — це розбиття його на трикутники, таке що:

• кожна вершина будь-якого трикутника є вершиною вихідного багатокутника;

• жодні два трикутники не мають додатної площі перетину;

• площа об'єднання всіх трикутників дорівнює площі вихідного багатокутника.

Вага тріангуляції визначається як сума ваг складових її трикутників, де вага трикутника дорівнює добутку міток його вершин.

Знайдіть мінімальну вагу серед усіх можливих тріангуляцій даного багатокутника.

Приклади

У першому тесті задано трикутник з вершинами $1,2,3$. Його вага дорівнює 1 \cdot 2 \cdot 3 = 6.

У другому тесті задано квадрат з вершинами 1, 2, 3, 4. Мінімальна вага досягається при тріангуляції з діагоналлю $(1,3)$:

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

Приклад 1

Loading

Loading

Приклад 2

Loading

Loading