Count of Unique Direct Path Between N Points On a Plane

0 0 2 minutes read

Given N points on a plane, where each point has a direct path connecting it to a different point, the task is to count the total number of unique direct paths between the points.

Note: The value of N will always be greater than 2.

Examples:

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.

Approach: The given problem can be solved using an observation that for any N-sided there are (number of sides + number of diagonals) direct paths. For any N-sided polygon, there are N sides and N*(N – 3)/2 diagonals. Therefore, the total number of direct paths is given by N + (N * (N – 3))/2.

Below is the implementation of the above approach:

C++

// 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

// 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

Python3

# 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#

// 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

Javascript

<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>

Output:

Time Complexity: O(1)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!