Written in C++, find the number of triangles formed by a set of points on three lines

Now we have several points present in the 3 rows; for example, we need to find out how many triangles these points can form

Input: m = 3, n = 4, k = 5
Output: 205

Input: m = 2, n = 2, k = 1
Output: 10

We will apply some combinations Mathematics to solve this problem and formulate some formulas to solve this problem.

Method to find solutions

In this method we will devise a formula: applying combinatorics to the current situation, this formula will provide us with the result.

C code for the above method

This is the C syntax we can use as input to solve the given problem -

Example

#include <bits/stdc++.h>

#define MOD 1000000007

using namespace std;

long long fact(long long n) {
   if(n <= 1)
   return 1;
   return ((n % MOD) * (fact(n-1) % MOD)) % MOD;
}
long long comb(int n, int r) {
   return (((fact(n)) % MOD) / ((fact(r) % MOD) * (fact(n-r) % MOD)) % MOD);
}

int main() {
   int n = 3;
   int m = 4;
   int r = 5;
   long long linen = comb(n, 3); // the combination of n with 3.
   long long linem = comb(m, 3); // the combination of m with 3.
   long long liner = comb(r, 3); //the combination of r with 3.
   long long answer = comb(n + m + r, 3); // all possible comb of n, m , r with 3.
   answer -= (linen + linem + liner);
   cout << answer << "\n";
   return 0;
}

Output

205

Explanation of the above code

In this method, we find all possible combinations of n m r and three numbers, that is, comb(n m r, 3). Now, you know that the condition for three points to become a triangle is that they cannot be collinear, so we find all possible collinear points obtained by summing the combinations of n, m, r, and then combine this sum with n m r By subtracting the changes in the three numbers, we get the answer and print it out.

Conclusion

This article discusses how to calculate how many triangles can be formed from a set of points on three lines by applying combinatorics. We also learned the C program and complete method (normal method) to solve this problem. We can write the same program in other languages ​​like C, Java, Python and others. Hope this article is helpful to you.

The above is the detailed content of Written in C++, find the number of triangles formed by a set of points on three lines. For more information, please follow other related articles on the PHP Chinese website!