Recuento de ruta directa única entre N puntos en un plano

Dados N puntos en un plano, donde cada punto tiene un camino directo que lo conecta a un punto diferente, la tarea es contar el número total de caminos directos únicos entre los puntos. 

Nota: El valor de N siempre será mayor que 2 .

Ejemplos:

Entrada: N = 4
Salida: 6
Explicación: Piense en 4 puntos como un polígono de 4 lados. Habrá 4 caminos directos (lados del polígono) así como 2 diagonales (diagonales del polígono). Por lo tanto, la respuesta será 6 caminos directos.

Entrada: N = 3
Salida:  3
Explicación: Piense en 3 puntos como un polígono de 3 lados. Habrá 3 caminos directos (lados del polígono) así como 0 diagonales (diagonales del polígono). Por lo tanto, la respuesta será 3 caminos directos.

Enfoque: El problema dado se puede resolver utilizando la observación de que para cualquier lado N hay (número de lados + número de diagonales) caminos directos. Para cualquier polígono de N lados, hay N lados y N*(N – 3)/2 diagonales. Por lo tanto, el número total de caminos directos viene dado por N + (N * (N – 3))/2 .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the total number
// of direct paths
int countDirectPath(int N)
{
    return N + (N * (N - 3)) / 2;
}
 
// Driver Code
int main()
{
 
    int N = 5;
    cout << countDirectPath(N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG
{
   
// Function to count the total number
// of direct paths
static int countDirectPath(int N)
{
    return N + (N * (N - 3)) / 2;
}
 
// Driver Code
public static void main(String []args)
{
 
    int N = 5;
    System.out.print(countDirectPath(N));
 
}
}
 
// This code is contributed by shivanisinghss2110

# python program for the above approach
 
# Function to count the total number
# of direct paths
def countDirectPath(N):
 
    return N + (N * (N - 3)) // 2
 
# Driver Code
if __name__ == "__main__":
 
    N = 5
    print(countDirectPath(N))
 
# This code is contributed by rakeshsahni

// C# program for the above approach
using System;
 
public class GFG
{
   
    // Function to count the total number
    // of direct paths
    static int countDirectPath(int N)
    {
        return N + (N * (N - 3)) / 2;
    }
     
    // Driver Code
    public static void Main(string []args)
    {
     
        int N = 5;
        Console.Write(countDirectPath(N));
     
    }
}
 
// This code is contributed by AnkThon

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to count the total number
        // of direct paths
        function countDirectPath(N) {
            return N + Math.floor((N * (N - 3)) / 2);
        }
 
        // Driver Code
        let N = 5;
        document.write(countDirectPath(N));
 
// This code is contributed by Potta Lokesh
    </script>

10

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)