Подсчет уникальных прямых путей между N точками на плоскости

Даны N точек на плоскости, где каждая точка имеет прямой путь, соединяющий ее с другой точкой, задача состоит в том, чтобы подсчитать общее количество уникальных прямых путей между точками.

Примечание . Значение N всегда будет больше 2 .

Примеры:

Input: N = 4
Output: 6
Explanation: Think of 4 points as a 4 sided polygon. There will 4 direct paths (sides of the polygon) as well as 2 diagonals (diagonals of the polygon). Hence the answer will be 6 direct paths.

Input: N = 3
Output:  3
Explanation: Think of 3 points as a 3 sided polygon. There will 3 direct paths (sides of the polygon) as well as 0 diagonals (diagonals of the polygon). Hence the answer will be 3 direct paths.

Подход: Данную задачу можно решить, используя наблюдение, что для любой N -стороны существуют (число сторон + число диагоналей) прямые пути. У любого N -стороннего многоугольника есть N сторон и N*(N – 3)/2 диагоналей. Таким образом, общее количество прямых путей равно N + (N * (N – 3))/2 .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)