Home > Backend Development > C++ > body text

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

王林
Release: 2023-09-09 09:53:08
forward
1247 people have browsed it

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
Copy after login

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;
}
Copy after login

Output

205
Copy after login

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!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!