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.
In this method we will devise a formula: applying combinatorics to the current situation, this formula will provide us with the result.
This is the C syntax we can use as input to solve the given problem -
#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; }
205
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.
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!