C ++を使用して、3本の線上の点のセットから形成された三角形の数を見つけます

現在、3行にいくつかのポイントがあります。たとえば、これらの点が形成できる三角形の数を見つける必要があります

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

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

この質問にいくつかの組み合わせ論を適用し、この問題を解決するためのいくつかの公式を作成します。

解決策を見つけるためのアプローチ

このアプローチでは、現在の状況に組み合わせ論を適用することによって式を考案し、この式によって結果が得られます。

上記のアプローチのC++コード

これが、与えられた問題を解決するための入力として使用できるC++構文です-

例

#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

上記のコードの説明

このアプローチでは、n + m + rと3つの可能なすべての組み合わせ、つまり、comb（n + m + r、3）を見つけます。さて、ご存知のように、3つの点が三角形であるための条件は、それらが同一線上にあるべきではないということです。したがって、n、m、rと3の組み合わせ、およびこの合計をn+m + rの変化で減算し、3で答えを取得し、それを出力します。

結論

この記事では、いくつかの組み合わせ論を適用することにより、3本の線上の点のセットからいくつの三角形を形成できるかについて説明しました。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。