Given an integer N which denotes the points on the circumference of a circle, the task is to find the number of quadrilaterals formed using these points.
Examples:
Input: N = 5
Output: 5
Input: N = 10
Output: 210
Approach: The idea is to use permutation and combination to find the number of possible quadrilaterals using the N points on the circumference of the circle. The number of possible quadrilaterals will be 
.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // number of quadrilaterals formed// with N distinct points#include<bits/stdc++.h>using namespace std;// Function to find the factorial// of the given number Nint fact(int n){ int res = 1; // Loop to find the factorial // of the given number for(int i = 2; i < n + 1; i++) res = res * i; return res;}// Function to find the number of// combinations in the Nint nCr(int n, int r) { return (fact(n) / (fact(r) * fact(n - r)));}// Driver Codeint main(){ int n = 5; // Function Call cout << (nCr(n, 4));}// This code is contributed by rock_cool |
Java
// Java implementation to find the // number of quadrilaterals formed// with N distinct pointsclass GFG{ // Function to find the number of// combinations in the Nstatic int nCr(int n, int r) { return (fact(n) / (fact(r) * fact(n - r)));}// Function to find the factorial// of the given number Nstatic int fact(int n){ int res = 1; // Loop to find the factorial // of the given number for(int i = 2; i < n + 1; i++) res = res * i; return res;}// Driver Codepublic static void main(String[] args){ int n = 5; // Function Call System.out.println(nCr(n, 4));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to find the # number of quadrilaterals formed# with N distinct points# Function to find the number of # combinations in the Ndef nCr(n, r): return (fact(n) / (fact(r) * fact(n - r))) # Function to find the factorial # of the given number Ndef fact(n): res = 1 # Loop to find the factorial # of the given number for i in range(2, n + 1): res = res * i return res # Driver Codeif __name__ == "__main__": n = 5 # Function Call print(int(nCr(n, 4))) |
C#
// C# implementation to find the // number of quadrilaterals formed// with N distinct pointsusing System;class GFG{ // Function to find the number of// combinations in the Nstatic int nCr(int n, int r) { return (fact(n) / (fact(r) * fact(n - r)));}// Function to find the factorial// of the given number Nstatic int fact(int n){ int res = 1; // Loop to find the factorial // of the given number for(int i = 2; i < n + 1; i++) res = res * i; return res;}// Driver Codepublic static void Main(String[] args){ int n = 5; // Function Call Console.Write(nCr(n, 4));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript implementation to find the // number of quadrilaterals formed // with N distinct points // Function to find the factorial // of the given number N function fact(n) { let res = 1; // Loop to find the factorial // of the given number for(let i = 2; i < n + 1; i++) res = res * i; return res; } // Function to find the number of // combinations in the N function nCr(n, r) { return (fact(n) / (fact(r) * fact(n - r))); } // Driver Code let n = 5; // Function Call document.write(nCr(n, 4)); // This code is contributed by Surbhi Tyagi.</script> |
5
Using nested loops :
Approach:
We can iterate over all possible combinations of 4 points and check if they form a quadrilateral. To check if a set of 4 points form a quadrilateral, we can check if any three points are not collinear. This can be done by checking if the cross product of two vectors formed by any three points is non-zero.
Define a function named count_quadrilaterals_2 that takes an integer argument N representing the number of distinct points on the circumference of the circle.
Initialize a variable count to 0 to keep track of the number of quadrilaterals.
Create a list points containing the integers from 0 to N-1 representing the distinct points on the circle.
Use four nested loops to iterate over all possible combinations of 4 points:
Loop over i from 0 to N-1
Loop over j from i+1 to N-1
Loop over k from j+1 to N-1
Loop over l from k+1 to N-1
Check if the four selected points (points[i], points[j], points[k], points[l]) form a quadrilateral:
Check if any three points are not collinear by computing the cross product of any two vectors formed by the three points.
If the cross products are non-zero, increment the count variable.
Return the final value of count.
C++
#include <iostream>using namespace std;int GFG(int N) { int count = 0; int points[N]; for (int i = 0; i < N; i++) { points[i] = i; } // Loop through all possible // combinations of 4 points for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { for (int k = j + 1; k < N; k++) { for (int l = k + 1; l < N; l++) { // Check if any three points are not collinear if ((points[j] - points[i]) * (points[k] - points[i]) != 0 && (points[j] - points[i]) * (points[l] - points[i]) != 0 && (points[k] - points[j]) * (points[l] - points[j]) != 0) { count++; } } } } } return count;}int main() { cout << GFG(5) << endl; cout << GFG(10) << endl; return 0;} |
Python3
def count_quadrilaterals_2(N): count = 0 points = [i for i in range(N)] for i in range(N): for j in range(i+1, N): for k in range(j+1, N): for l in range(k+1, N): # Check if any three points are not collinear if (points[j]-points[i])*(points[k]-points[i]) != 0 and \ (points[j]-points[i])*(points[l]-points[i]) != 0 and \ (points[k]-points[j])*(points[l]-points[j]) != 0: count += 1 return count # Example usageprint(count_quadrilaterals_2(5)) # Output: 5print(count_quadrilaterals_2(10)) # Output: 210 |
C#
using System;class Program{ static int GFG(int N) { int count = 0; int[] points = new int[N]; // Initialize the points array for (int i = 0; i < N; i++) { points[i] = i; } // Loop through all possible combinations of 4 points for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { for (int k = j + 1; k < N; k++) { for (int l = k + 1; l < N; l++) { // Check if any three points are not collinear if ((points[j] - points[i]) * (points[k] - points[i]) != 0 && (points[j] - points[i]) * (points[l] - points[i]) != 0 && (points[k] - points[j]) * (points[l] - points[j]) != 0) { count++; } } } } } return count; }// Driver code static void Main(string[] args) { Console.WriteLine(GFG(5)); Console.WriteLine(GFG(10)); }} |
Javascript
function countQuadruples(N) { let count = 0; const points = new Array(N); // Initialize an array with values [0, 1, 2, ..., N-1] for (let i = 0; i < N; i++) { points[i] = i; } // Loop through all possible combinations of 4 points for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { for (let k = j + 1; k < N; k++) { for (let l = k + 1; l < N; l++) { // Check if any three points are not collinear if ( (points[j] - points[i]) * (points[k] - points[i]) !== 0 && (points[j] - points[i]) * (points[l] - points[i]) !== 0 && (points[k] - points[j]) * (points[l] - points[j]) !== 0 ) { count++; } } } } } return count;}// Example usage:console.log(countQuadruples(5)); // Output: 10console.log(countQuadruples(10)); // Output: 210 |
5 210
Time Complexity: O(N^4)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!